Граф, у якому всі вершини з'єднані ребрами, називається неорієнтованим. Ланцюг – шлях по вершинах і ребрах, що включає будь-яке ребро графа не більше одного разу. Цикл – ланцюг, початкова і кінцева вершини якого збігаються.
Шлях та ланцюг у графі Шлях чи цикл називають простим, якщо ребра у ньому не повторюються. Якщо у графі будь-які дві вершини з'єднані шляхом, то такий граф називається зв'язковим.
Граф називається повним, якщо будь-які дві різні вершини з'єднані одним і тільки одним рубом. У повному графі кожна вершина належить одному й тому ж числу ребер, оскільки вона з'єднана з усіма іншими вершинами. Для завдання повного графа достатньо знати його число вершин.
Зміст
- 1.1 Простий граф
- 1.2 Псевдограф
- 1.3 Мультиграф
- 1.4 Псевдомультіграф
- 1.5 Орієнтований граф
- 1.6 Змішаний граф
- 1.7 Ізоморфні графи
- 1.8 Інші пов'язані визначення