- •Курсовая работа по курсу «Комбинаторика»
- •Курсовая работа по курсу «Модулярная арифметика»
- •Курсовая работа по курсу «Графы»
- •2 4 E3
- •Алгоритм построения совершенного паросочетания для двудольного графа.
- •X1 y1
- •X1 y1 Шаг 4.
- •Алгоритм построения совершенного паросочетания в полном нагруженном двудольном графе.
- •X1 y1 x1 0 3 4 3
- •4X1 y1 0 x1 x1 x2
- •7 X2 y2 0 y3 y3
- •8 X3 y3 0
- •7 X4 y4 0
- •3X1 y1 0 x2 x1 x2 x3
- •6 X2 y2 0 y2 y3 y2
- •8 X3 y3 1
- •7 X4 y4 0
- •3X1 y1 0 x3 x1 x2 x3
- •3X1 y1 0 x4 x1 x1 x3 x4
- •6 X2 y2 0 y2 y1 y4 y1
- •7 X3 y3 1 x1
- •6 X4 y4 0 y4
- •3 X1 y1 0
- •6 X2 y2 0
- •7 X3 y3 1
- •6 X4 y4 0
- •Приложение
Курсовая работа по курсу «Графы»
Студент Фадеев М.А.
Группа А-06-08
Преподаватель Набебин А.А.
Москва 2010
Задание 1.21 Для данного неориентированного графа написать маршрут, цепь, простую цепь, цикл, простой цикл, матрицу смежностей (соседства вершин) и матрицу инциденций (принадлежности вершин и ребер). Преобразовать данный неориентированный граф в ориентированный и написать для него ормаршрут, путь, простой путь, контур, простой контур, матрицу смежностей и матрицу инциденций.
G = (V, E) = (V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1, 5), (1, 6), (1, 7), (1, 9), (2, 4), (2, 5), (2, 6),
(2, 7), (3, 4), (3, 5), (3, 6), (3, 9), (4, 8), (4, 9), (6, 8), (7, 8), (7, 9)}).
Решение:
Степени вершин:
deg(1) = 4, deg(2) = 4, deg(3) = 4,
deg(4) = 4,тdeg(5) = 3, deg(6) = 4,
deg(7) = 4, deg(8) = 3, deg(9) = 4
Маршрут:
1-9-3-4-8-7-1-6-2-7-1-5-2-6-8-4-2-5-3-4-9
е1-е16-е9-е12-е17-е15-е2-е4-е10-е11-е14-е7-е8-е17-е13-е5-е6-е1-е3
1е1-5е16-3е9-9е12-7е17-8е15-6е2-1е4-9е10-4е11-3е14-6е7-2е8-7е17-8е13-4е5-2е6-5е1-1е3
Цепь:
1-9-7-8-6-3-5-2-4
е4-е12-е17-е15-е14-е16-е6-е7-е8-е3-е12-е10-е11-е9
1е4-9е12-7е17-8е15-6е14-3е16-5е6-2е7-2е8-1е3-7е12-9е10-4е11-3е9
Простая цепь:
1-5-3-9-7-8-4-2-6
е1-е16-е9-е12-е17-е13-е5-е7
1е1-5е16-3е9-9е12-7е17-8е13-4е5-2е7
Цикл:
1-9-7-8-6-3-4-2-5-1
е4-е12-е17-е15-е14-е11-е5-е6-е1
1е4-9е12-7е17-8е15-6е14-3е11-4е5-2е6-5е1
Простой цикл:
1-9-7-8-4-2-5-1
е4-е12-е17-е13-е11-е16-е6-е7-е2
1е4-9е12-7е17-8е13-4е11-3е16-5е6-2е7-6е2
Матрица смежностей: Матрица инциденций:
1 2 3 4 5 6 7 8 9 е1 е2 е3 е4 е5 е6 е7 е8 е9 е10 е11 е12 е13 е14 е15 е16 е17
┌ ┐ ┌ ┐
1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 1 1 1 1 0 0 2 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0
3 0 0 0 1 1 1 0 0 1 3 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0
А = 4 0 1 1 0 0 0 0 1 1 , B = 4 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0
5 1 1 1 0 0 0 0 0 0 5 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0
6 1 1 1 0 0 0 0 1 0 6 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0
7 1 1 0 0 0 0 0 1 1 7 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1
8 0 0 0 1 0 1 1 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
9 1 0 1 1 0 0 1 0 0 9 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0
└ ┘ └ ┘
Ориентированный граф:
G = (V, E) = (V={1, 2, 3, 4, 5, 6, 7 , 8, 9}, E= {(1, 2), (2, 4), (3, 4), (4, 5), (1, 5), (3, 7), (5, 6), (6, 7)}).
Степени вершин:
deg(1) = 3, deg(2) = 2, deg(3) = 3,
deg(4) = 2, deg(5) = 3, deg(6) = 2,
deg(7) = 3.
Ормаршрут:
124376515673
е1 е2 е3 е8 е7 е6 е5 е4 е6 е7 е9
1е1 2е2 4е3 3е8 7е7 6е6 5е5 1е4 5е6 6е7 7е93
Путь:
737651243
е9 е8 е7 е6 е5 е1 е2 е3
7е9 3е8 7е7 6е6 5е5 1е1 2е2 4е3 3
Простой путь:
1243765
е1 е2 е3 е8 е7 е6
1е1 2е2 4е3 3е8 7е7 6е6 5
Контур:
7376512437
е9 е8 е7 е6 е5 е1 е2 е3 е8
7е9 3е8 7е7 6е6 5е5 1е1 2е2 4е3 3е8 7
Простой контур:
12437651
е1 е2 е3 е8 е7 е6 е5
1е1 2е2 4е3 3е8 7е7 6е6 5е5 1
Матрица смежностей: Матрица инциденций:
┌ ┐ ┌ ┐
1 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0
2 0 0 0 1 1 0 1 0 1 2 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0
3 0 0 1 1 1 0 0 0 1 3 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0
А = 4 0 1 1 0 0 0 0 1 1 , B = 4 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0
5 1 1 1 0 0 0 0 0 0 5 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0
6 1 1 1 0 0 0 0 1 0 6 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0
7 1 1 0 0 0 0 0 1 1 7 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1
8 0 0 0 1 0 1 1 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
9 1 0 1 1 0 0 1 0 0 9 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0
└ ┘ └ ┘
Задание 2.21
Найти кратчайший путь между вершинами s=v1, t=v4 в нагруженном связно ориентированном графе
G=(V,E)=(V={v1,v2,v3,v4,v5,v6,v7,v8,v9}, E={{v1,v2,8}, (v1,v7,8),{v1,v8,4},{v1,v9,2},{v2,v3,8},{v2,v7,2},{v2,v9,6},{v3,v4,2},{v3,v6,4},(v3,v9,2),(v4,v5,0), (v4,v6,2),{v4,v7,6},(v5,v6,2),{v6,v7,8},{v6,v8,4},{v6,v9,2},{v7,v9,6},{v8,v9,2}}).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вес wij ребра {vi,vj} или дуги (vi,vj) равен N(i2+j2)+ i2+j2 +i+j по модулю 10 (остаток от деления wij на 10). N есть номер варианта (N=21).
Неориентированные ребра (проходимые в обоих направлениях) указаны в фигурных скобках, ориентированные ребра указаны в круглых скобках. Третья координата ребра есть его вес.
Помечивающий алгоритм (Дейкстры) поиска кратчайшего (с наименьшим весом) пути между двумя вершинами s и t в связном нагруженном ориентированном графе.
1.Вычисление наименьшего веса пути от s к t.
Присвоим вершине s постоянную (подчеркнутую) пометку 0. Вершину s объявляем активной и помечаем знаком плюс. Всем остальным вершинам присвоим временные (неподчеркнутые) пометки ∞. Переход к шагу 2.
Если пометка вершины t постоянна (подчеркнута), то алгоритм заканчивает работу. Пометка вершины t равна весу кратчайшего пути от s к t. Постоянные пометки других вершин равны весам кратчайших путей от s к t. Если пометка вершины t временная, то переход к шагу 3.
Изменим временные пометки вершин v, соседних (по дугам) с активной, следующим образом. Присваиваем вершине v временную пометку, равную сумме пометки активной вершины и веса дуги , идущей в вершину v из активной вершины, если эта сумма меньше, чем существующая временная пометка вершины v. В противном случае оставим у вершины v прежнюю пометку. Переход к шагу 4.
Среди всех остальных вершин с временными пометками найдем вершину с наименьшей пометкой. Если таких вершин несколько, то возьмем любую из них, объявив её постоянной, а эту вершину - новой активной вершиной, которую помечаем знаком плюс. Прежняя активная вершина свой плюс теряет. Переход к шагу 2.
Построение наименьшего пути от s к t.
Кратчайший путь от s к t соответствует(в обратном порядке) начинающейся в t и заканчивающейся в s любой последовательности вершин, в которой каждая предыдущая вершина смежна (по дуге) с последующей, при чем разность между пометками соседних вершин последовательности равна весу ребра, соединяющему эти вершины.
Решение:
Шаг 1. Присвоим вершине s=v1 постоянную пометку 0. Остальные вершины получают временные пометки ∞. Вершину s=v1 объявляем активной и помечаем знаком плюс. Переход к шагу 2.
Шаг 2. Вершина t=v4 постоянной пометки не имеет. Переход к шагу 3.
Шаг 3. Среди всех вершин с временными пометками соседние с активной вершиной s=v1 с пометкой 0 вершины v2, v9,v8,v7 имеют временные пометки ∞. Для v2: 0+8=8<∞ ;v9: 0+2=2<∞;v8: 0+4=4<∞; v7: 0+8=8<∞;. Присваиваем для v2, v9,v8,v7 новые временные пометки 8 ,2,4,8 соответственно. Переход к шагу 4
.
Шаг 4. Из всех временных пометок пометка 2 для v9 наименьшая. Объявляем пометку 2 для вершины v9 постоянной, вершину v9объявляем активной и помечаем знаком плюс. Вершина v1 свой плюс теряет. Переход к шагу 2
Шаг 2. Вершина t=v4 постоянной пометки не имеет. Переход к шагу 3.
Шаг 3. Среди всех вершин с временными пометками соседние с активной вершиной s=v9 с пометкой 2 вершины v2,v6,v8 имеют временные пометки 8 , ∞, 4. Для v2: 2+6=8<8 ;v7: 2+3=6<8;
v9: 3+1=4<6 Присваиваем для v3 , v7, v9 новые временные пометки 12, 6,4. Переход к шагу 4.
Шаг 4. Из всех временных пометок пометка 2 для v8 наименьшая. Объявляем пометку 2 для вершины v8 постоянной, вершину v8 объявляем активной и помечаем знаком плюс. Вершина v9 свой плюс теряет. Переход к шагу 2
Шаг 2. Вершина t=v4 постоянной пометки не имеет. Переход к шагу 3.
Шаг 3. Среди всех вершин с временными пометками соседние с активной вершиной s=v9 с пометкой 4 вершина v6,v7 , v8 имеют временные пометки ∞ ,6,9. Для v6: 4+1=5<∞ ; 4+6=10>6;
v8: 4+7=11>9. Присваиваем для v6 новую временную пометку 5. Переход к шагу 4.
Шаг 4. Из всех временных пометок пометка 5 для v6 наименьшая. Объявляем пометку 5 для вершины v6 постоянной, вершину v6 объявляем активной и помечаем знаком плюс. Вершина v9 свой плюс теряет. Переход к шагу 2
Шаг 2. Вершина t=v4 постоянной пометки не имеет. Переход к шагу 3.
Шаг 3. Среди всех вершин с временными пометками соседние с активной вершиной s=v6 с пометкой 5 вершины v3,v7 ,v8 имеют временные пометки 12, 6,9. Для v3: 5+9=14>12 ;
v7: 5+3=8>6, v7: 5+4=9>=9.
Шаг 4. Из всех временных пометок пометка 6 для v7 наименьшая. Объявляем пометку 6 для вершины v7 постоянной, вершину v7 объявляем активной и помечаем знаком плюс. Вершина v2 свой плюс теряет. Переход к шагу 2
Шаг 2. Вершина t=v4 постоянной пометки не имеет. Переход к шагу 3.
Шаг 3. Среди всех вершин с временными пометками соседняя с активной вершиной s=v7 с пометкой 6 вершина v4 имеет временную пометку ∞ . Для v4: 6+1=7<∞. Присваиваем для v4 новую временную пометку 7. Переход к шагу 4.
Шаг 4. Из всех временных пометок пометка 7 для v4 наименьшая. Объявляем пометку 7 для вершины v4 постоянной, вершину v4 объявляем активной и помечаем знаком плюс. Вершина v7 свой плюс теряет. Переход к шагу 2
Шаг 2. Пометка 7 вершины t=v4 постоянна. Алгоритм заканчивает работу. Пометка 7 вершины t равна весу кратчайшего пути из s в t.
Построение кратчайшего пути от s к t.
Пусть f-1(v) есть множество всех вершин v’, смежных с v; d(v)есть пометка вершины v; c(vi,vj) есть вес ребра (vi,vj).
f-1(t)={v3,v5,v6, v7}, d(t)-d(v3)=7-12=-5≠7=c(v3,t); d(t)-d(v5)=7-∞≠2; d(t)-d(v6)=7-5≠6; d(t)-d(v7)=7-1=1=c(v7,t)=1.
v7,t есть последовательность кратчайшего пути.
f-1(v7)={v2, v9}, d(v7)-d(v2)=6-3=3=c(v2,v7)=3; d(v7)-d(v9)=6-4=2≠c(v6,v3)=6;
f-1(v2)={s,v9}, d(v2)-d(v9)=3-4= -1≠c(v9,v2)=1; d(v2)-d(s)=3-0=3=c(s,v2)=3;
s,v9,v6, ,v7,t есть кратчайший путь от s к t.
Ответ: Путь s=v1→ v9→ v6→ v7=t от s к t кратчайший.
Его (наименьший ) вес есть 4.
Задание 3.21
Проверить, является ли граф из задачи 1 эйлеровым (если граф не эйлеров, то достроить его до эйлерова графа) и найти в нем эйлеров цикл.
Алгоритм 1.
Выбираем цикл в G:
С1 = 2352;
G1 = G − С1 = {(1, 2), (1, 6), (2, 6), (3, 4), (3, 6), (4, 5), (5, 6)}.
Выбираем цикл в G1:
С2 = 63456; G2 = G1 − С2 = {(1, 2), (1, 6), (2, 6)}.
Выбираем цикл в G2:
С3 = 1261; G3 = G2 − С3 = .
Из циклов С1, С2, С3 комбинируем эйлеров цикл. Выбираем два цикла
С1 = 2352, С2 = 63456 с общей вершиной 3; получаем цикл С4 = 23456352. Циклы С4, С3 объединяем по общей вершине 6; получаем С5 = 23456126352. Цикл С5 является эйлеровым циклом.
Алгоритм 2.
Эйлеров цикл в четном графе можно построить, начав его любым ребром, а затем последовательно надстраивая его вправо смежными ребрами, одновременно удаляя выбранные ребра из графа и следя за тем, чтобы при очередном удалении ребра из графа он не распался на несвязные компоненты, или не очутились в изолированной вершине, не исчерпав при этом всех ребер графа.
Построим эйлеров цикл в эйлеровом графе G = (V, E) с множеством вершин V = {1, 2, 3, 4, 5, 6, 7, 8} и следующими ребрами:
е1 = (1, 2), е2 = (2, 8), е3 = (8, 6), е4 = (6, 4), е5 = (4, 2), е6 = (2, 3), е7 = (3, 4),
е8 = (4, 5), е9 = (5, 6), е10 = (6, 7), е11 = (7, 8), е12 = (8, 1).
Мы перечислили ребра в порядке их удаления из графа. Построенная последовательность ребер е1, е2, е3, …, е12 составляет эйлеров цикл. Заметим, что после удаления ребра е4 нельзя убрать ребро е8 , ибо полученный тогда граф распадается на две несвязнын компонент. После удаления ребра е2 нельзя удалять ребро е12 , ибо тогда мы попадаем в изолированную вершину 1, не исчерпав всех ребер графа.
Решение:
е1 = (1, 2), е2 = (2, 3), е3 = (3, 4), е4 = (4, 5),
3
e1
е5 = (5, 6), е6 = (6, 7), е7 = (7, 8), е8 =(1, 8),
e2
е9 = (1, 6), е10 = (5 ,8), е11 = (2, 5), е12 = (2, 7),
2
4
e3
е13 = (3, 6), е14 = (3, 8), е15 = (4, 7), е16 = (1, 4).
e11
e13
e14
e1
e4
e12
e15
Степени вершин:
e16
deg(1) = 4, deg(2) = 4, deg(3) = 4, deg(4) = 4,
1
5
e9
deg(5) = 4, deg(6) = 4, deg(7) = 4,deg(8)=4
e5
e8
e10
6
e6
Маршрут:
8
e7
7
1-2-7-4-1-6-3-8-5-2-3-4-5-6-7
е1 е12 е15 е16 е9 е13 е14 е10 е11 е2 е3 е4 е5 е6
1е1 2е12 7е15 4е16 1е9 6е13 3е14 8е10 5е11 2е2 3е3 4е4 6е5 7е6
Граф G = (V, E) называется эйлеровым, если все вершины имеют четную степень. Данный граф – эйлеров граф.
С1 = 2-3-4-5-1-2 (е2, е3, е4, е11, е1), G1 = G − С1 = {(5, 6), (6, 7), (2, 7), (2, 4), (1, 4), (3 ,7), (4, 6), (1, 6), (4, 7), (3, 5)}.
3
е8
2 4
е10
е7 е9
1
е15
е14 е12
5
е13
7 е6 е5
6
G1 = (V, E1)
С2 = 1-4-6-1 (е12 , е9, е13), G2 = G1 − С2 = {(5, 6), (6, 7), (2, 7), (2, 4), (3 ,7),
(4, 7), (3, 5)}.
3
2 е8 4
е10
1 е7 е14
е15
5
7 е6 е5
6
G2 = (V, E2)
С3 = 7-2-4-7 (е7, е8, е14), G3 = G2 − С3 = {(5, 6), (6, 7), (3 ,7), (3, 5)}.
3
2 4
е10 е15
1
5
7 е6 е5
6
G3 = (V, E3)
С4 = 5-6-7-3-5 (е15, е5, е6 , е10), G4 = G3 − С4 = .
3
2 4
1
7 5
6
G4 = (V, E4)
Эйлеров цикл:
С1 = 2-3-4-5-1-2
С2 = 1-4-6-1
С3 = 7-2-4-7
С4 = 5-6-7-3-5
С13 = 7-2-3-4-5-1-2-4-7
С123 = 7-2-3-4-5-1-4-6-1-2-4-7
С1234 = 7-2-3-4-5-6-7-3-5-1-4-6-1-2-4-7
Ответ: Эйлеров цикл: С1234 = 7-2-3-4-5-6-7-3-5-1-4-6-1-2-4-7
Задание 4.21
В ненагруженном графе G из задачи 1 с помощью алгоритма удаления циклических ребер найти фундаментальную систему циклов и соответствующие множество хорд, каркас, все фундаментальные сечения (разрезы). По теореме Кирхгофа найти число каркасов данного графа.
Решение:
е1 = (1, 2), е2 = (2, 3), е3 = (3, 4), е4 = (4, 5),
3
e1
е5 = (5, 6), е6 = (6, 7), е7 = (7, 8), е8 =(1, 8),
e2
е9 = (1, 6), е10 = (5 ,8), е11 = (2, 5), е12 = (2, 7),
2
4
e3
е13 = (3, 6), е14 = (3, 8), е15 = (4, 7), е16 = (1, 4).
e11
e13
e14
e1
e4
e12
e15
Степени вершин:
e16
deg(1) = 4, deg(2) = 4, deg(3) = 4, deg(4) = 4,
1
5
e9
deg(5) = 4, deg(6) = 4, deg(7) = 4,deg(8)=4
e5
e8
e10
6
e6
Маршрут:
8
e7
7
1-2-7-3-2-4-3-5-4-6-1-4-7-6-5
е1 е7 е10 е2 е8 е3 е15 е4 е12 е13 е9 е14 е6 е5
1е1 2е7 7е10 3е2 2е8 4е3 3е15 5е4 4е12 6е13 1е9
4е14 7е6 6е5
Граф |
Простой цикл |
Удаляемое ребро из рассматриваемого цикла |
G |
С1 = 2-3-4-5-1-2 |
е1 = (1, 2) |
G1 = G − е1 |
С2 = 7-3-5-6-7 |
е10 = (3, 7) |
G2 = G1 − е10 |
С3 = 3-4-5-6-7-2-3 |
е3 = (3, 4) |
G3 = G2 − е3 |
С4 = 7-2-3-5-6-7 |
е15 = (3, 5) |
G4 = G3 − е15 |
С5 = 2-4-5-6-7-2 |
е8 = (2, 4) |
G5 = G4 − е8 |
С6 = 7-4-5-6-7 |
е6 = (6, 7) |
G6 = G5 − е6 |
С7 = 1-4-5-6-1 |
е13 = (1, 6) |
G7 = G6 − е13 |
С8 = 1-4-5-1 |
е9 = (1, 4) |
G8 = G7 − е9 |
С9 = 4-5-6-4 |
е4 = (4, 5) |
G9 = G9 − е4 – есть каркас графа G.
Фундаментальная система циклов: {С1, С2, С3, С4, С5, С6, С7, С8, С9};
Множество хорд: H = {е1, е10, е3, е15, е8, е6, е13, е9, е4};
Все фундаментальные сечения (разрезы): H{(2, 3)}, H{(5, 6)}, H{(2, 7)}, H {(1, 5)}, H {(4, 6)}, H {(4, 7)}.
3
e2