1. Домогтися відсутності у графа циклів. Цикломатичне число завжди невід'ємне. Основна властивість цикломатичного числа формулюється у вигляді теореми: Цикломатичне число мультиграфа дорівнює максимальному числу незалежних циклів.Jan 20, 2011
Хроматичним числом графа називається мінімальне число квітів, якими можна правильно розфарбувати вершини графа. Неважко бачити, що зображений вище граф Петерсен не можна правильно розфарбувати в два кольори, оскільки в ньому є цикли непарної довжини. Отже, його хроматичне число дорівнює 3.
Центром графа називається така вершина, що максимальна відстань між нею та будь-якою іншою вершиною є найменшою з усіх можливих; ця максимальна відстань називається радіусом графа.
Зміст
- 1.1 Простий граф
- 1.2 Псевдограф
- 1.3 Мультиграф
- 1.4 Псевдомультіграф
- 1.5 Орієнтований граф
- 1.6 Змішаний граф
- 1.7 Ізоморфні графи
- 1.8 Інші пов'язані визначення