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

Для кожного графа можна визначити ряд кількісних характеристик, які пов’язані з його структурою, властивостями та необхідні для різних розрахунків, зокрема визначення ізоморфізму графів.

Найпростішими кількісними показниками графа G є кількості n(G) вершин та m(G) ребер, набори степенів (напівстепенів) вершин. Зв’язність графа характеризується кількістю q(G) його зв’язних компонент (зв’язних підграфів). Три зі згаданих показників визначають циклохроматичне число графа l(G)=m(G)–n(G)+q(G). Циклохроматичне число тісно пов’язане з кількістю циклів, які можна побудувати на графі. В теорії графів розроблен методи визначення параметра q(G). Для зв’язного графа без циклів q(G)=1, l(G)=0.

Розглянемо характеристику графа, яка називається хроматичним числом. Уявімо, що граф вершинно розфарбований різними кольорами. Хроматичне число g(G) дорівнює мінімальній кількості кольорів, якими можна розфарбувати вершини графа таким чином, що ніякі дві суміжні вершини не будуть зафарбовані однаковим кольором (рис. 3.19).

В теорії графів доведено, що будь-який планарний граф можна розфарбувати п’ятьма фарбами так, щоб ніякі дві суміжні вершини не були одного кольору (хроматичне число не перевищує 5). Таке розфарбування графа називають правильним. Існує гіпотеза (досі не доведена), що будь-який планарний граф, зображений діаграмою на площині, можна розфарбувати правильно чотирма кольорами (проблема чотирьох фарб).

Для реберно розфарбованих графів визначають хроматичний клас (індекс) графа. Хроматичний клас c(G) дорівнює мінімальній кількості фарб, якими можна правильно розфарбувати ребра графа.

Якщо граф містить багато вершин та ребер, то підбір мінімальної кількості фарб важко здійснити. В такому разі для визначення хроматичного числа або класу застосовуються спеціальні алгоритми, які є в “арсеналі” цілочисельного лінійного програмування.

Різноманітні задачі, що виникають при плануванні виробництва, складанні графіків ремонту обладнання або перевезень товарів і т.д., часто можуть бути подані як задачі розфарбування графів.

Тут ми розглянули лише головні числові характеристики графів. В теорії графів розроблено ще багато інших числових характеристик, причому повного їх переліку поки не визначено. Важливими задачами теорії графів є вираження складних для обчислення числових характеристик (хроматичного числа, хроматичного класу та ін.) через такі, що легко визначаються (кількості вершин та ребер, циклохроматичне число, степені та напівстепені вершин тощо).

Розділ 4 СКІНЧЕННІ АВТОМАТИ

Автомат – це пристрій, що виконує свої функції без участі людини. Теорія автоматів як наукова дисципліна виникла в межах теорії керуючих систем в середині ХХ століття, в період бурхливого розвитку засобів електронної обчислювальної техніки та відповідних областей математичного знання. На сьогодні ця теорія є одним із розділів дискретного аналізу.

Розвиток інформаційних технологій вивів сферу застосування теорії автоматів далеко за рамки моделювання апаратних засобів цифрової електроніки, розширивши її до фундаментальних основ сучасної теоретичної інформатики. Сьогодні абстракції і моделі, розроблені в теорії автоматів, затребувані такими науковими дисциплінами як теорія алгоритмів, теорія формальних граматик, математична лінгвістика, теорія логічних моделей, теорія кодування, теорія обчислювальної складності та іншими.

Теорію автоматів, як теоретико-прикладну науку, умовно поділяють на теорію абстрактних автоматів та теорію структурних автоматів, перша з яких є теоретичною базою другої. Математичні моделі в теорії абстрактних автоматів розглядають пристрої дискретної дії з точки зору алгоритмів їх функціонування, тобто послідовностей дій з перетворення дискретної інформації. Під час абстрактного аналізу та синтезу автомата головну роль грає не спосіб побудови автомата, а ті переходи зі стану в стан, які робить автомат під впливом вхідних сигналів, і ті вихідні сигнали, які автомат при цьому формує. Предметом дослідження теорії структурних автоматів є структурно-функціональна організація автоматів як технічних засобів реалізації їх математичних моделей. Під структурним аналізом і синтезом автомату мається на увазі розгляд структури самого автомата, його вхідних і вихідних сигналів, а також дослідження способів його побудови з набору логічних елементів і елементарних автоматів, способів кодування внутрішніх станів і т.і.

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

Задача аналізу полягає в тому, щоб по заданому автомату описати його поведінку або за неповними даними про алгоритм функціонування автомата встановити його властивості.

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

Задача еквівалентних перетворень формулюється наступним чином: визначити повну систему правил, що дозволяє перетворювати довільний автомат в еквівалентний йому автомат. Окремим випадком даної задачі є перехід від однієї моделі автомата до іншої.

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