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