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

Задачі

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

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

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

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

Визначити цикломатичне число для графів, заданих матрицями суміжності (табл. 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, визначити їхнэ число зовнішньої стійкості.

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

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

Абстрактний автомат. Робота автомата. Способи завдання

Задачі

Лічильник, на вхід якого подаються двоїчні цифри 0 і 1, підраховує за модулем 3 загальне число одиниць, що надійшли на його вхід, необхідно:

визначити вхідний, вихідний алфавіти і безліч станів;

записати таблицю переходів-виходів відповідного автомата;

побудувати граф автомата і його матрицю з'єднань (суміжності);

визначити тип автомата.

Побудувати таблиці переходів-виходів і матриці з'єднань (суміжності) для автоматів А₁, А₂ (рис. 5.1.).

Рис. 5.1. Графи автоматів А₁ і А₂

Текст в алфавіті з 32 букв і пропусків між словами сканується для підрахунку слів, що починаються з букви «а» і закінчуються на букви «ія». Букви, крім «а», «і», «я» позначаються через «a», пропуск - через «b». Вхідний і вихідний алфавіти, безліч станів рівні: X = {а, і, я, a, b}, Y = {вважати, не вважати}, S = {нове слово, поява «а...,» поява «а...і», поява «а...ія», чекання нового слова}. Необхідно:

записати таблицю переходів-виходів відповідного автомата;

побудувати граф автомата і його матрицю з'єднань (суміжності);

визначити тип автомата.

Автомат А₃ заданий матрицею з'єднань (табл. 5.1.), необхідно:

визначити безліч станів, вхідний і вихідний алфавіти;

записати таблицю переходів-виходів відповідного автомата;

побудувати граф автомата і визначити тип автомата;

знайти наскрізний, ізольований і тупиковий подавтоматы для А₄.

Таблиця 5.1

	0/1Ú1/0
		0/0		1/1
			0/1Ú1/1
			0/1		1/0
			0/1					1/1
						0/1Ú1/0
					1/0			0/1
						0/0Ú1/1

Визначити, які з автоматів А₄, А₅, А₆ (рис. 5.2.), є еквівалентними.

Рис. 5.2. Автомати А₄, А₅, А₆

На входи однорозрядного послідовного суматора подаються розряди двох доданків у коді 0 чи 1, а виходом є розряд суми за модулем 2. Суматор має два стани, обумовлені значеннями переносу (0 чи 1). Показати, що суматор можна представити автоматами А₇, А₈ (рис. 5.3.).

Рис. 5.3. Автомати Мура А₇ і Мілі А₈

Розширення функцій d і l

Задачі

На підставі автомата А₉ (рис. 5.4.) визначити вихідну послідовність і послідовність станів при початковому стані 3 і вхідній послідовності:

(0, 1, 2, 3, 3, 0, 1, 2);

(2, 0, 1, 3, 2, 0, 0, 2);

(3, 1, 0, 0, 2, 3, 0, 2, 1, 1);

(2, 3, 3, 0, 1, 2, 1, 1, 0, 3);

(3, 1, 2, 0, 1, 1, 2, 2, 0, 3).

Рис. 5.4. Граф автомата А₉

Для автомата, побудованого в задачі 3, визначити вихідну послідовність і послідовність станів, якщо на вхід при початковому стані «нове слово» подаються слова:

«арія», «диня», «армія»;

«оказія», «агонія», «аркебуза»;

«анатомія», «антифриз», «астрономія»;

Для автоматів А₇, А₈ задачі 6 (рис. 5.3) визначити вихідні послідовності і зміни станів при підсумовуванні чисел:

35 і 17;

28 і 21;

12 і 43;

19 і 38;

8 і 51.