Задачі, які приводять до поняття графа, Детальна інформація

Визначення 3. Граф, що складається тільки з ізольованих вершин, називається нуль-графом.

Визначення 4. Граф, у якому кожна пара вершин з'єднана ребром, називається повним.

Визначення 5. Ступенем вершини називається число ребер, яким належить вершина.

Визначення 6. Граф, ступеня всіх k вершин якого однакові, називається однорідним графом ступеня k.

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

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

Визначення 9. Багатокутник плоского графа, що не містить усередині себе ніяких чи вершин ребер графа, називають його гранню.

Визначення 10. Шляхом від A до X називається послідовність ребер, що веде від A до X, така, що кожні два сусідніх ребра мають загальну вершину, і ніяке ребро не зустрічається більш одного разу.

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

Визначення 12. Простим циклом називається цикл, що не проходить ні через одну з вершин графа більш одного разу.

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

Визначення 14. Дві вершини A і B у графі називаються зв'язковими (незв'язними), якщо в ньому існує (не існує) шлях, що веде з A у B.

Визначення 15. Граф називається зв'язковим, якщо кожні дві його вершини зв'язні; якщо ж у графі знайдеться хоча б одна пара незв'язних вершин, то граф називається незв'язним.

Визначення 16. Деревом називається зв'язний граф, що не містить циклів.

Тривимірною моделлю графи-дерева служить, наприклад, дійсне дерево з його хитромудро розгалуженою кроною; ріка і її припливи також утворять дерево, але вже плоске – на поверхні землі.

Визначення 17. Незв'язний граф, що складається винятково з дерев, називається лісом.

Визначення 13. Дерево, усі n вершин якого мають номера від 1 до n, називають деревом з перенумерованими вершинами.

Отже, ми розглянули основні визначення теорії графів, без яких було б неможливе доказ теорем, а, отже і рішення задач.

Використана література:

Основи вищої математики. – К., 2002.

Математична енциклопедія. – М., 1989.