Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Тема. Теория графов.






Вопросы программы: Графы, виды графов. Вершины и ребра графа. Степень вершины. Теорема Эйлера о рукопожатиях. Операции над графами. Изоморфизм графов. Эйлеровы и гамильтоновы графы. [1] (c. 189-193), [3] (c.241-253).

Представления графов в ЭВМ. Матрицы смежности и инцидентности. Списки смежности. Массивы дуг. Обходы графа в ширину и глубину. [1] (c. 201-203), [3] (c.265-269).

Маршруты, цепи циклы графов. Геодезические цепи. Разделяющее множество. Теорема Менгера. Связность графа. [1] (c. 195-197), [3] (c.253).

Укладки графов, планарность. Формула Эйлера. Деревья и их свойства, каркасы. Основная теорема о деревьях. Алгоритмы Краскала и Дейкстры. [1] (c. 234-259), [3] (c.289-304).

Раскраска графа. Хроматическое число. Теорема о пяти красках. Гипотеза о четырех красках. [1] (c. 281-289), [3] (c.277-283).

Решение типовых задач

Задача 1. Установите, являются ли указанные графы изоморфными?

 

Решение: Занумеруем вершины одного из графов в произвольном порядке цифрами, а другого буквами. Требуется установить, существует ли биективное отображение вершин первого и второго графов, при котором каждому ребру одного графа будет соответствовать ребро другого графа.

Перебирать все возможные биекции (а их ровно 9!) слишком долго и нерационально, поэтом воспользуемся тем фактом, что степени вершин при изоморфизме не изменяются.

Составим схему степеней вершин первого графа (первое число номер вершины, второе число степень вершины): 1-2, 2-2, 3-2, 4-2, 5-3, 6-2, 7-2, 8-3, 9-4.

Составим схему степеней вершин второго графа: a-2, b-2, c-2, d-2, e-3, f-2, g-2, h-4, k-2.

Если изоморфизм графов существует, то вершине 9 первого графа соответствует вершина h второго.

Вершина 9 первого графа смежная с вершинами 5 и 8 степени 3. Вершина h второго графа смежная вершинам e и f степени 3. Следовательно, вершины 5 и 8 изоморфны вершинам e и f. Пусть 5 изоморфна e, а 8 изоморфна f.

Вершина 9 первого графа изоморфна двум вершинам 6 и 7 степени 2. Вершина h второго графа смежная вершинам g и k степени 2. Следовательно, вершины 6 и 7 изоморфны вершинам g и k. Пусть 6 изоморфна g, а 7 изоморфна k.

Для вершины 5 первого графа осталась вершина 3 степени 2, которая должна соответствовать вершине c, а для вершины 4 соответствует вершина d.

Остается две вершины 1 и 2, которые изоморфны вершинам a и b.

Таким образом, установим изоморфизм: 1®a, 2®b, 3®c, 4®d, 5®e, 6®g, 7®k, 8®f, 9®h.

Тогда (1, 2)®(a, b), (1, 3)®(a, c), (2, 4)®(b, d), (3, 5)®(c, e), (4, 8)®(d, f), (5, 6)®(e, g), (7, 8)®(k, f), (5, 9)®(e, h), (6, 9)®(g, h), (7, 9)®(k, h) и (8, 9)®(f, h).

Следовательно, графы изоморфны.

Задача 2. Для данного графа найти максимальное количество геодезических цепей, соединяющих вершины 1, 25 и разделяющее множество, содержащее минимальное количество вершин.

Решение: Для того, чтобы построить максимальное количество геодезических цепей, будем строить их по следующему правилу. Смежные вершины включены в цепь, если эти вершины не включены ни в одну ранее построенную геодезическую цепь и последующая вершина лежит по возможности «выше» предыдущей.

Строим первую геодезическую цепь: 1-2 (вершина 2 смежная вершине 1 и лежит «выше»), 2-5-12-18-20-25.

Строим вторую геодезическую цепь: 1-3-8-13 (вершину 5 выбрать нельзя, так как она принадлежит первой цепи) 13-15-19-24-25.

Строим третью геодезическую цепь: 1-6-11-16-22 (вершину 19 выбрать нельзя, так как она принадлежит второй цепи) 22-23-25.

Строим четвертую геодезическую цепь: 1-10-14-17-25.

Построить пятую геодезическую цепь нельзя, так как цепь, проходящая через вершину 4, обязательно пройдет через вершину 10, которая входит в четвертую цепь.

Итак, максимальное количество геодезических цепей – четыре.

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

Пятую геодезическую цепь невозможно было построить, так как она должна была пройти через 10 вершину. Поэтому включим ее в разделяющее множество.

Для того чтобы найти вторую вершину разделяющего множества, выберем на третьей геодезической цепи вершину таким образом, чтобы нельзя было попасть в вершину 25 с помощью цепи, не смежной первой и второй геодезической цепям. Такой вершиной является вершина 6 (если взять вершину 11, то существует обходной путь 6-9-14).

Для того чтобы найти третью вершину разделяющего множества, выберем на второй геодезической цепи вершину таким образом, чтобы нельзя было попасть в вершину 25 с помощью цепи, не смежной первой геодезической цепям. Такой вершиной является вершина 3 (если взять вершину 8, то существует обходной путь 3-11).

Четвертую вершину выберем на первой геодезической цепи, это вершина 2 (если взять вершину 5, то существует обходной путь 2-8).

Итак, разделяющее множество S={10, 6, 3, 2}.

Задача 3. Для данного графа составить матрицу смежности, матрицу инцидентности. Провести поиски в глубину и в ширину.

Решение: Для того чтобы составить, матрицу смежности определим вначале размерность матрицы. Так как граф содержит 9 вершин, то матрица смежности будет состоять из 9 строк и 9 столбцов. Если существует ребро (i, j), то в матрице на i-ой строке в j-ом столбце будет находиться символ 1, если такого ребра нет, то символ 0. В итоге получим:

Для того чтобы составить матрицу инцидентности необходимо занумеровать ребра графа: (1, 2) – I, (1, 5) – II, (2, 3) – III, (2, 5) – IV, (2, 6) –V, (3, 4) – VI, (3, 7) – VII, (6, 8) – VIII, (6, 9) – IX, (8, 9) – X.

Так как граф содержит 10 ребер, матрица инцидентности будет состоять из 9 строк и 10 столбцов. Если ребро i инцидентно вершине j, то в i-ой строке j-ом столбце матрицы будет находиться символ 1, если ребро i не инцидентно вершине j, то в i-ой строке j-ом столбце матрицы будет находиться символ 0. В итоге получим:

Для поиска в глубину или ширину введем понятие очереди. Если есть некоторая вершина, то по отношению к ней зададим упорядоченное множество вершин, смежных ей в порядке возрастания номера. Если в это множество необходимо добавить вершину, то она вносится в конец очереди.

Для поиска в глубину необходимо задать упорядоченное множество всех вершин графа, по следующему правилу: начинаем перечисление с первой вершины. Для нее зададим множество всех вершин, ей смежных и упорядочим по возрастанию номеров. Из полученной очереди извлечем номер первой вершины и перенесем его в искомое, упорядоченное множество, а в очередь добавим все вершины смежные изъятой, не содержащиеся в очереди. Продолжим процесс, пока искомое множество не будет содержать всех вершин графа, а очередь будет пустой.

  2, 5
1, 2 5, 3, 6
1, 2, 5 3, 6
1, 2, 5, 3 6, 4, 7
1, 2, 5, 3, 6 4, 7, 8, 9
1, 2, 5, 3, 6, 4 7, 8, 9
1, 2, 5, 3, 6, 4, 7 8, 9
1, 2, 5, 3, 6, 4, 7, 8 9
1, 2, 5, 3, 6, 4, 7, 8, 9  

 

Поиск в глубину: 1, 2, 5, 3, 6, 4, 7, 8, 9.

Для того, чтобы задать поиск в ширину, необходимо в алгоритме поиска в глубину из очереди извлекать последний номер. Таким образом, получим:

  2, 5
1, 5 2
1, 5, 2 3, 6
1, 5, 2, 6 3, 8, 9
1, 5, 2, 6, 9 3, 8
1, 5, 2, 6, 9, 8 3
1, 5, 2, 6, 9, 8, 3 4, 7
1, 5, 2, 6, 9, 8, 3, 7 4
1, 5, 2, 6, 9, 8, 3, 7, 4  

Поиск в ширину: 1, 5, 2, 6, 9, 8, 3, 7, 4.

Задание 4. Для заданного графа составить остовый подграф наименьшего веса с помощью алгоритма Краскала.

3 4

5 2 7

4 2 6 3 3

5 2 3 1

1 3 5 3 2 4

4 5 3

 

Решение: Для решения задачи упорядочим все ребра графа по весу в порядке убывания: (7, 12) – 7, (5, 7) – 6, (1, 5) – 5, (4, 5) – 5, (5, 6) – 5, (6, 10) – 5, (1, 2) – 4, (3, 6) – 4, (4, 7) – 4, (9, 10) – 4, (2, 4) – 3, (3, 5) – 3, (6, 8) – 3, (7, 8) – 3, (9, 11) – 3, (9, 12) – 3, (10, 11) – 3, (2, 5) – 2, (7, 9) – 2, (8, 9) – 2, (8, 10) – 2, (1, 3) – 1, (11, 12) – 1.

Начинаем выбирать ребра из перечисленных ребер в обратном порядке. Последнее ребро выбирается всегда (11, 12). Каждое последующее ребро выбирается в том случае, если его выбор не образует циклов в новом подграфе. Так следующее ребро (1, 3) тоже выбираем. Выбранные ребра рекомендуется выделять на исходном графе другим цветом. Аналогично выбираем следующие ребра: (8, 10), (8, 9), (7, 9), (2, 5), (10, 11). Ребро (9, 12) выбрать нельзя, так как образуется цикл: 9-8-10-11-12. Продолжаем выбор: (9, 11), (7, 8) – нельзя; (6, 8), (3, 5), (2, 4) выбираем; (9, 10) – нельзя; (4, 7) выбираем; (7, 12), (5, 7), (1, 5), (4, 5), (5, 6), (6, 10), (1, 2), (3, 6).

Для контроля, количество выбранных ребер в связном конечном графе равно количеству вершин минус один, то есть в нашем случае 12 -1=11.

Для определения веса выбранного подграфа, достаточно просуммировать веса выбранных ребер: 1+1+2+2+2+2+3+3+3+3+4=26.

Замечание: Если начать выбор с первого ребра (вес этого ребра самый большой), то по указанному алгоритму можно выбрать подграф максимального веса.

Задание 5. Для заданного графа найти путь из вершины 1 в вершину 12 наименьшего веса.

3 4 7

2 5 6 2 3

4 5 2 1 3 1

3 2 2

1 5 3 4

4 5

Решение: Решение состоит в пересчете меток для каждой вершины. Для этого каждой вершине ставим в соответствие первоначальную метку ¥. Далее определим два множества: множество вершин P, метки которых не окончательные; множество вершин T, метки которых окончательны (минимальны).

Вначале P=Æ, T={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.

1 шаг. Поместим во множество P первую вершину пути 1 с меткой 0, удаляя эту вершину из множества T, и пересчитаем метки всех вершин, в которые можно попасть из вершин множества P (1). Из вершины 1 можно попасть в вершину 2 за 4. То есть вершине 2 ставим в соответствие новую метку 4. Аналогично, вершине 5 метку 2, вершине 3 метку 1.

2 шаг. Из всех вершин множества T выбираем вершину, метка которой самая наименьшая (если таких вершин несколько, то можно выбрать произвольную), и перемещаем ее во множество P. Для остальных вершин множества T пересчитаем все метки.

Продолжаем этот процесс до тех пор, пока во множество P не войдут все вершины, а множество T станет пустым. Процесс пересчета и выбора меток оформим в виде таблицы:

                       
¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥
0 ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥
      ¥   ¥ ¥ ¥ ¥ ¥ ¥ ¥
    1 ¥     ¥ ¥ ¥ ¥ ¥ ¥
  4         ¥ ¥ ¥ ¥ ¥ ¥
        4     ¥ ¥ ¥ ¥ ¥
          5     ¥   ¥ ¥
      7         ¥   ¥ ¥
              8     ¥ ¥
                9      
            10          
                  10    
                    12  
                      12

3 шаг. Метка последней вершины равна 12. Следовательно, длина кратчайшего пути из вершины 1 в вершину 12 равна 12. Восстановим этот путь. В вершину 12 за 12 можно попасть из вершины 9. В вершину 9 можно попасть за 9 из вершины 8. В вершину 8 можно попасть за 8 из вершины 6. В вершину 6 можно попасть за 5 из вершины 3. В вершину 3 за 1 можно попасть из вершины 1. Таким образом, искомый путь: 1 – 3 – 6 – 8 – 9 – 12.

Задание 6. Для заданного графа найти максимальный поток и разрез минимального веса.

s

14 12

16 17

13 9 4 3 10

5 10 7 6 5

11 11

17 13 17

 

t

Решение: Для решения задачи необходимо перебрать все возможные вершинно не пересекающиеся простые цепи из истока s в сток t. На каждой такой цепи определить дугу с минимальной пропускной способностью, с учетом предыдущих цепей и добавить каждой дуге найденную величину.

Если все возможные цепи построены и определены величины потока для каждой дуги, то из множества всех дуг, в которых величина потока равна пропускной способности можно составить разрез, такой, что его вес будет равен величине потока. Тогда по теореме Форда-Фалкерсона, найденный поток будет максимальным, а соответствующий разрез – минимальным.

Для определения путей занумеруем вершины графа:

14 12

13 16 17

9 4 3 10

5 10 7 6 5

17 11 13 11 17

 

Начинаем перебирать все возможные цепи либо «справа» либо «слева» на выбор. Выберем вариант перебора цепей «справа».

Первая возможная цепь: s-1-5-t. Дуга минимального веса – (1, 5) с пропускной способностью 13. Поэтому всем дугам этой цепи (s, 1), (1, 5), (5, t) сопоставим величину потока равную 13. Отметим, что ребро (1, 5) максимально загружено, и значит, его нельзя использовать в остальных цепях.

14 13 12

13 16 17

13 9 4 3 10

5 10 7 6 5

17 11 13 11 17

13

 

 

Вторая возможная цепь: s-1-6-t. С учетом предыдущей цепи дуга минимального веса – (s, 1) с пропускной способностью 14-13=1. Поэтому всем дугам этой цепи (s, 1), (1, 6), (6, t) сопоставим величину потока равную 1. Отметим, что ребро (s, 1) максимально загружено, и значит, его нельзя использовать в остальных цепях.

14 13+1 12

13 16 17

13 9 1 4 3 10

5 10 7 6 5

1

17 11 13 11 17

13

 

Третья возможная цепь: s-3-6-t. С учетом предыдущих цепей дуга минимального веса – (3, 6) с пропускной способностью 5. Поэтому всем дугам этой цепи (s, 3), (3, 6), (6, t) сопоставим величину потока равную 5. Отметим, что ребро (3, 6) максимально загружено, и значит, его нельзя использовать в остальных цепях.

14 13+1 12

13 5 16 17

13 9 1 4 3 10

5 5 10 7 6 5

1+5

17 11 13 11 17

13

 

 

Четвертая возможная цепь: s-3-7-t. С учетом предыдущих цепей дуга минимального веса – (3, 7) с пропускной способностью 10. Поэтому всем дугам этой цепи (s, 3), (3, 7), (7, t) сопоставим величину потока равную 10. Отметим, что ребро (3, 7) максимально загружено, и значит, его нельзя использовать в остальных цепях.

 

14 13+1 12

13 5+10 16 17

13 9 1 4 3 10

5 510 10 7 6 5

1+5

17 11 13 11 17

13 10

 

Пятая возможная цепь: s-4-7-t. С учетом предыдущих цепей дуга минимального веса – (7, t) с пропускной способностью 13-10=3. Поэтому всем дугам этой цепи (s, 4), (4, 7), (7, t) сопоставим величину потока равную 3. Отметим, что ребро (7, t) максимально загружено, и значит, его нельзя использовать в остальных цепях.

14 13+1 12

13 5+10 16 3 17

13 9 1 4 3 10

5 510 10 3 7 6 5

1+5

17 11 10+3 11 17

13 13

 

Шестая возможная цепь: s-4-8-t. С учетом предыдущих цепей дуга минимального веса – (4, 8) с пропускной способностью 4. Поэтому всем дугам этой цепи (s, 4), (4, 8), (8, t) сопоставим величину потока равную 4. Отметим, что ребро (4, 8) максимально загружено, и значит, его нельзя использовать в остальных цепях.

 

14 13+1 12

13 5+10 16 3+4 17

13 9 14 4 3 10

5 510 10 3 7 6 5

1+5 4

17 11 10+3 11 17

13 13

 

Седьмая возможная цепь: s-2-8-t. С учетом предыдущих цепей дуга минимального веса – (2, 8) с пропускной способностью 3. Поэтому всем дугам этой цепи (s, 2), (2, 8), (8, t) сопоставим величину потока равную 3. Отметим, что ребро (2, 8) максимально загружено, и значит, его нельзя использовать в остальных цепях.

14 13+13 12

13 5+10 16 3+4 17

13 9 14 4 3 3 10

5 510 10 3 7 6 5

1+5 4+3

17 11 10+3 11 17

13 13

 

 

Восьмая возможная цепь: s-2-9-t. С учетом предыдущих цепей дуга минимального веса – (s, 2) с пропускной способностью 12-3=9. Поэтому всем дугам этой цепи (s, 2), (2, 9), (9, t) сопоставим величину потока равную 9. Отметим, что ребро (s, 2) максимально загружено, и значит, его нельзя использовать в остальных цепях.

 

14 13+13+9 12

13 5+10 16 3+4 17 9

13 9 14 4 3 3 10

5 510 10 3 7 6 5

1+5 4+3

17 11 10+3 11 17

13 13 9

 

 

Так как больше нельзя построить цепей, не используя максимально нагруженные дуги, найдем величину потока, которая равна полустепени исхода истока или полустепени захода стока: 14+15+7+12=48 или 13+6+13+7+9=48.

Из выделенных ребер составим разрез с весом 48: (s, 1) – 14; (3, 6) – 5; (7, t) – 13; (4, 8) – 4; (s, 2) -12. Вес равен: 14+5+13+4+12=48.

 

Задание 7. Для заданного графа составить код Хамари и найти каноническую нумерацию вершин графа.

 
 


Решение:

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

 
 

 


Упорядочим множество всех вершин, смежных с вершиной 1 по степени, и занумеруем их в соответствии с этим порядком: 2, 3, 4, 5, 6.

 
 


Упорядочим множество всех вершин, смежных с пронумерованными (помеченными) вершинами по степени: 7, 8.

 
 

 

 


Полученное расположение вершин является каноническим.

Найдем код Хамари

Получим код 1111100110010010000010100011.

Задание 8. Для заданного графа определить, является ли он Эйлеровым или квазиэйлеровым и найти соответствующий цикл или цепь.

   
 
 
 


Решение: Граф является эйлеровым, если четны степени всех его вершин, квазиэйлеровым, если только две вершины графа имеют нечетную степень.

Для построения эйлерова цикла выбирается произвольная вершина графа, строится произвольный цикл. Далее для произвольной вершины цикла, не все инцидентные ребра которой входят в цикл, строим новый цикл, не проходящий через ребра уже проведенного цикла (такой цикл существует по теореме Эйлера). Продолжаем построение таких циклов до тех пор, пока не будут задействованы все ребра графа. Объединив все построенные циклы, получим эйлеров цикл.

Занумеруем все вершины графа:

 
 

 


Так как степени всех вершин четные, то существует эйлеров цикл. Выберем произвольную вершину 1. И построим цикл 1-2-3-4-9-8-7-6-1. Выберем вершину 2 и построим новый цикл 2-5-7-2. Выберем вершину 3 и построим новый цикл 3-5-8-3.

Так как все ребра графа задействованы, осталось составить эйлеров цикл. Для этого в первый цикл вместо вершины 2 вставляем второй цикл, а вместо вершины 3 третий, в итоге получим: 1-2-5-7-2-3-5-8-3-4-9-8-7-6-1 – эйлеров цикл.

Задание 9. Для заданного помеченного дерева составить код Прюфера и по полученному коду восстановить исходное дерево.

 
 


Решение: Так как граф – дерево, то он содержит, по крайней мере, две «висячие» вершины. Выпишем множество висячих вершин, в порядке их нумерации {1, 6, 7, 9, 10} и выберем висячую вершину с наименьшим номером – 1. Единственную смежную ей вершину внесем в код Прюфера – 2, а саму вершину удалим из графа. Получим новое дерево.

 
 


Выпишем множество висячих вершин, в порядке их нумерации {6, 7, 9, 10} и выберем висячую вершину с наименьшим номером – 6. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, а саму вершину удалим из графа. Получим новое дерево.

 
 


Выпишем множество висячих вершин, в порядке их нумерации {7, 8, 9, 10} и выберем висячую вершину с наименьшим номером – 7. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, 3, а саму вершину удалим из графа. Получим новое дерево.

 
 


Выпишем множество висячих вершин, в порядке их нумерации {3, 8, 9, 10} и выберем висячую вершину с наименьшим номером – 3. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, 3, 2, а саму вершину удалим из графа. Получим новое дерево.

 
 


Выпишем множество висячих вершин, в порядке их нумерации {2, 8, 9, 10} и выберем висячую вершину с наименьшим номером – 2. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, 3, 2, 4, а саму вершину удалим из графа. Получим новое дерево.

       
 
   


Выпишем множество висячих вершин, в порядке их нумерации {8, 9, 10} и выберем висячую вершину с наименьшим номером – 8. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, 3, 2, 4, 4, а саму вершину удалим из графа. Получим новое дерево.

 
 


Выпишем множество висячих вершин, в порядке их нумерации {9, 10} и выберем висячую вершину с наименьшим номером – 4. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, 3, 2, 4, 4, 4, а саму вершину удалим из графа. Получим новое дерево.

 
 


Выпишем множество висячих вершин, в порядке их нумерации {4, 10} и выберем висячую вершину с наименьшим номером – 4. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, 3, 2, 4, 4, 4, 5, а саму вершину удалим из графа. Получим новое дерево.

 

 
 


Выпишем множество висячих вершин, в порядке их нумерации {5, 10} и выберем висячую вершину с наименьшим номером – 5. Единственную смежную ей вершину внесем в код Прюфера – 2, 8, 3, 2, 4, 4, 4, 5, 10, а саму вершину удалим из графа. Получим новое дерево.

 
 


Так как полученное дерево состоит из единственной вершины, код Прюфера закончен – 2, 8, 3, 2, 4, 4, 4, 5, 10.

Произведем распаковку кода Прюфера.

Так как код Прюфера – 2, 8, 3, 2, 4, 4, 4, 5, 10 содержит 9 элементов, то в соответствующем графе 10 вершин.

Нанесем эти вершины на плоскость произвольным образом:

 
 


Составим множество вершин графа, неиспользованных в коде: T={1, 6, 7, 9}

Соединим неиспользованную вершину с наименьшим номером – 1, с первой вершиной кода – 2, т.е. получили ребро (1, 2).

Вершину 1 удалим из множества T, а вершину 2 удалим из кода, так как вершина 2 присутствует в оставшейся части кода, то не вносим ее во множество T.

Получим: Код - 8, 3, 2, 4, 4, 4, 5, 10.

T={6, 7, 9}.

Аналогично получим ребро (6, 8).

Получим: Код - 3, 2, 4, 4, 4, 5, 10.

T={7, 8, 9} – (7, 3).

Код - 2, 4, 4, 4, 5, 10.

T={3, 8, 9} – (2, 3).

Код - 4, 4, 4, 5, 10.

T={2, 8, 9} – (4, 2).

Код - 4, 4, 5, 10.

T={8, 9} – (4, 8).

Код - 4, 5, 10.

T={9} – (4, 9).

Код – 5, 10.

T={4} – (5, 4).

Код - 10.

T={5} – (5, 10).

Так как код закончился, то полученный граф – искомое дерево.

Непосредственной проверкой, нетрудно показать, что полученный граф и исходное дерево изоморфны.

Задания для самостоятельной работы

1. Установите, являются ли указанные графы изоморфными?

1.1.

 

 

1.2.

 

 

1.3.

 

1.4.

 

1.5.

 

 

1.6.

 

1.7.

 

 

1.8.

 

 

1.9.

 

 

1.10.

 

2. Для данного графа найти максимальное количество геодезических цепей, соединяющих вершины 1, 25 и разделяющее множество, содержащее минимальное количество вершин.

2.1.

 

 

2.2.

 

2.3.

 

 

2.4.

 

 

2.5.

 

2.6.

 

 

2.7.

 

2.8.

 

 

2.9.

 

2.10.

 

3. Для данного графа составить матрицу смежности, матрицу инцидентности. Провести поиски в глубину и в ширину.

3.1.

 

 

3.2.

 

 

3.3.

 

 

3.4.

 

3.5.

 

 

3.6.

 

 

3.7.

 

3.8.

 

 

3.9.

 

 

3.10.

 

4. Для заданного графа составить остовый подграф наименьшего веса с помощью алгоритма Краскала.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.