Чисельні характеристики графів

Задачі

Визначити формулу, за якою через число вершин обчислюється ступінь вершини повного графа.

Визначити формулу, за якою через число ребер обчислюється ступінь вершини повного графа.

Визначити мінімальний ступінь вершини потужнозв’язаного орієнтованого графа.

Визначити максимальний ступінь вершини однорідного слабозв’язаного орієнтованого графа.

Визначити цикломатичне число для графів, заданих матрицями суміжності (табл. 4.11., 4.12., 4.13.):

Таблиця 4.11

	x1	x2	x3	x4
x1
x2
x3
x4

Таблиця 4.12

	x1	x2	x3	x4
x1
x2
x3
x4

Таблиця 4.13

	x1	x2	x3	x4
x1
x2
x3
x4

Визначити формулу, за якою обчислюється цикломатичне число повного графа як n(G) = f(n), де n – число вершин графа.

Визначити хроматичне число графів, заданих множинами фактор-безлічей:

F_G1 = ({x₂, x₃}, {x₁, x₄}, {x₁, x₄, x₅}, {x₂, x₃, x₅}, {x₃, x₄});

F_G2 = ({x₁, x₄}, {x₃, x₄}, {x₁, x₂, x₅}, {x₃, x₄});

F_G3 = ({x₂, x₃}, {x₁, x₃, x₄}, {x₁, x₂, x₅}, {x₂, x₅, x₆}, {x₃, x₄, x₆}, {x₄, x₅}).

Визначити хроматичне число графів G1, G2, G3 (рис. 4.4.):

Рис. 4.4. Графи G1, G2, G3

Записати можливі безлічі внутрішньої стійкості для графів, приведених у задачі 7, визначити їхнє число внутрішньої стійкості.

Знайти залежності, по яких визначається число внутрішньої стійкості повних графів, однорідних графів, нуль-графів, дерев.

Записати можливі безлічі зовнішньої стійкості для графів, приведених у задачі 7, визначити їхнэ число зовнішньої стійкості.

Знайти залежності, по яких визначається число зовнішньої стійкості повних графів, однорідних графів, нуль-графів, дерев.

КІНЦЕВІ АВТОМАТИ