Лекція №5

Home Alone Together

Child Custody

· In divorce proceedings, Middle Eastern men usually assume they are the most appropriate parent to have custody over the children.

· In most Middle Eastern marriages, the father's opinion will more likely prevail, since he is considered superior to his wife.

• A traditional unmarried Latina should not be alone in the com­pany of a man.

In conclusion I’d like to say that gender discrimination is an important problem throughout the world. In the United States a survey of men and women showed that most women were quite angry about being treated as inferiors by men. Most of the female respondents in the survey could cite specific examples of discrimination. In comparison, men were not interested in talking about their discrimination against women. The men acknowledged that gender discrimination occurred, but they were not bothered by it. Women in the United States receive an average salary that is three-fourths that of men. In other words, if a man and a woman both perform the same job, the male is paid $1.00 while the female is paid 75 cents. Stated another way, women with a university degree are paid the equivalent of what men earn who have only a high school degree. The feminist movement in the United States, inspired by the Civil Rights movement and using some of its strategies, seeks to end gender discrimination.

Тема: Графи. Пошук у графі. Пошук у глибину. Пошук у ширину. Обходи графу. Топологічне сортування.

План

1. Графи.

2. Пошук у графі.

3. Пошук у глибину.

4. Пошук у ширину.

5. Обходи графу.

6. Топологічне сортування.

Литература

1. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0

2. Меженный О.А. Turbo Pascal

3. Павловская Т.А. Паскаль. Программирование на языке высокого уровня

4. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с.

5. Фаронов В.В. Turbo Pascal 7.0. Практика программирования

6. Фаронов В.В. Turbo Pascal 7.0. Учебный курс

7. Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с.

8. Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с.

9. http://www.intuit.ru/

Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V,E). Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.

Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.

Матрица смежности - это двумерный массив размерности N*N.

A[i,j]=

Для хранения перечня ребер необходим двумерный массив R размерности M*2. Строка массива описывает ребро.

Пусть дан граф. Представим данный граф в языке Паскаль в виде матрицы смежности и перечня ребер.

uses crt;

const n=6;

a:array[1..n,1..n] of integer=

((0,2,0,0,3,0),

(0,0,0,0,0,3),

(0,0,0,0,0,2),

(5,0,0,0,0,4),

(0,6,0,0,0,0),

(0,0,0,0,0,0));

var matpreber:array[1..3,1..20] of integer;

i,k,j:integer;

procedure matreb;

begin

k:=0;

for i:=1 to n do

for j:=1 to n do

if a[i,j]<>0 then begin

k:=k+1;

matpreber[1,k]:=i;

matpreber[2,k]:=j;

matpreber[3,k]:=a[i,j];

end;

end;

procedure print;

begin

for i:=1 to 3 do

begin

for j:=1 to k do

write(matpreber[i,j],' ');

writeln;

end;

end;

begin

clrscr;

matreb;

print;

readkey;

end.

Массив а является для данного графа массивом смежности с указанием веса ребер. Массив matpreber является массивом перечня ребер, который получен из матрицы смежности. K есть степенью графа, т.е число инцидентных ребер. Этими двумя двумерными массивами можно идентифицировать любой граф.

Перед началом рассмотрения основных алгоритмов обработки графов введем основные определения в графах. Если в графе имеется ребро (u,v), говорят, что вершина v смежна с вершиной u. Для неориентированного графа отношение смежности является симметричным, но для ориентированных графов это необязательно. Степенью вершины в неориентированном графе называется число инцидентных ей ребер. Для ориентированного графа различают исходящую степень, определяемую как число выходящих из него ребер, и входящую степень, определяемую как число входящих в нее ребер. Сумма исходящей и входящей степеней называется степенью вершины. Путь называется простым, если все вершины в нем различны. Подпуть - это некоторое количество идущих подряд вершин этого пути. Циклом в ориентированном графе называется путь, в котором начальная вершина совпадает с конечным и который содержит хотя бы одно ребро. Цикл называется простым, если в нем нет одинаковых вершин (кроме первой и последней),т.е. если все вершины различны. Граф, в котором нет циклов называется ациклическим. Неориентированный граф называется связным, если для любой пары вершин существует путь из одной в другую. Ориентированный граф называется сильно связанным, если из любой вершины достижима любая другая.

Дата добавления: 2014-01-11