Вариант 7. Построить все неизоморфные простые несвязные графы вершинами и. компонентами связности

  • ID: 33234 
  • 14 страниц

Фрагмент работы:

Задание №1

Построить все неизоморфные простые несвязные графы с 5 вершинами и 2 компонентами связности.

Решение:

[image] [image] [image] [image] [image] [image] [image]

Задание №2

Какие из трех указанных графов являются изоморфными, а какие – неизоморфными? Для изоморфных графов указать соответствие вершин, сохраняющее смежность. Для неизоморфных пояснить причину этого.

[image] [image] [image]

G1 G2 G3

Решение:

2

2

2

Пронумеруем вершины:

5

5

4

4

3

3

1

1

5

4

3

1

[image] [image] [image]

G1 G2 G3

Построим матрицы смежности:

[image]

[image]

[image]

Проанализируем матрицы смежности. В первом и третьем графах 1 вершина имеет степень 2, а все остальные имеют степень 3, а во втором графе 2 вершины имеют степень 2, 2 вершины имеют степень 3 и 1 вершина имеет степень 4. Значит, граф G2 является неизоморфным. Матрицы смежности изоморфных графов получаются друг из друга одновременными перестановками строк и столбцов. В матрице смежности графа G3 переставим местами 1 и 2 строки и 1 и 2 столбцы:

[image]

Теперь переставим местами 2 и 4 столбцы и 2 и 4 строки:

[image]

Следовательно, первый и третий графы изоморфны. Соответствие вершин графов:

Задание №3

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

[image]

Решение:

[image]

[image]

Реберный граф:

[image]

[image]

Задание №4

Два колеса, степень центральных вершин которых равна =42 и =52, соединили ребром. Найти вершинное хроматическое число полученного графа.

Вершинное хроматическое число колеса с четной степенью центральных вершин равно [image]:

[image]

Если ребро соединяет центральные вершины двух колес, то есть они становятся смежными, то вершинное хроматическое число будет равно [image]:

[image]

В противном случае значение вершинного хроматического числа не измениться и будет равно [image]:

[image]

Задание №5