Самостійна робота Графи Знайдіть шлях, простий шлях, цикл, простий цикл в графі G1. Вкажіть Ейлерів та Гамільтонів шлях та цикл в графі G1, якщо є (відповідь обґрунтуйте).

Самостійна робота "Графи"

1. Знайдіть шлях, простий шлях, цикл, простий цикл в графі G1.
2. Вкажіть Ейлерів та Гамільтонів шлях та цикл в графі G1, якщо є (відповідь обґрунтуйте).
3. Знайдіть матрицю суміжності, матрицю інцидентності для графа G1.
4. Використовуючи матрицю суміжності знайдіть всі шляхи довжини 2 в графі G1.
5. Перевірте граф G1 на планарність, відповідь аргументуйте.
6. Знайдіть діаметр графів G1, G2
7. Знайдіть хроматичний многочлен та хроматичне число графів G1 та G2.

	C

Граф G1 Граф G2

1. Шлях: 1,2,3,8,6

Простий шлях: 2,4,5,6,7

Цикл: 1,2,4,3,1,7,6,5,4,3,1

Простий цикл: 1,2,4,5,6,7,1

1. Ейлерів шлях: 2,4,3,1,7,6,5,8

Ейлерів цикл: не існує бо не всі вершини є парними

Гамільтонів шлях: 1,2,3,4,5,6,7

Гамільтонів цикл: 2,1,7,6,5,4

1. Матриця суміжності: Матриця інцидентності:

A
B
C
D
E
F
G

1. Використовуючи матрицю суміжності знаходимо всі шляхи довжини 2:

ABC; BDF;

BCD; CDF;

DEF; DFA;

EFA;

FAB;

1. Оскільки в графа G1 немає ребер що перетинаються він є планарним і плоским.

1. Побудуємо матрицю відстаней між вершинами щоб знайти діаметр:

Отже діаметр графа G1 дорівнює 3, а графа G2 - 2

1. K-1

   

   K-1

   K

   Хроматичний многочлен графа G2 матиме вигляд: λ_G2(K) = K(K-1)², а хроматичне число K дорівнюватиме 2.

Оскільки граф G1 є складним то виконаємо для нього операції спрощення, а саме вилучення та стягнення ребер.

e

G1 G2=G1- e

K-2

e

G3= G1\ e G4=G3- e

				K-1

K-1

K-1

λ_G4(K) = K(K-1)³ (K-2)

K

K-1

G5=G3- e G6=G2- e

		K-1

K-1

K-2

K-2

K

		K-1
	K-1
		K-2

λ_G5(K) = K(K-1) (K-2)² λ_G6(K) = K(K-1)⁴ (K-2)

λ_G7(K) = K(K-1)² (K-2) ²

λ_G3(K) =(K(K-1)³ (K-2))-(K(K-1) (K-2)²)

λ_G2(K) = (K(K-1)⁴ (K-2))-(K(K-1)² (K-2) ²)

λ_G1(K) =((K(K-1)⁴ (K-2))-(K(K-1)² (K-2) ²))-((K(K-1)³ (K-2))-(K(K-1) (K-2)²))=

= K(K-1)((K-2)((K-1)³-(K-1)2(K-2))-((K-1)²-(K-2))) - хроматичний многочлен графа G1.

K	λ(K)
	>0
	>0

Виходячи з наведеної таблиці можна зробити висновок, що хроматичне число графа G1дорівнює 3.

Дата добавления: 2015-09-29