Основные понятия теории графов
   Теория графов, как было сказано выше, - дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.
    Определение 1. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.
    Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек.
   В дальнейшем вершины графа мы будем обозначать латинскими буквами А, В, С, D. Иногда граф в целом будем обозначать одной заглавной буквой.
  Определение 2. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.
  Определение 3. Граф, состоящий только из изолированных вершин, называется нуль-графом.
    Обозначение: О' - граф с вершинами, не имеющий ребер.
   Определение 4. Граф, в котором каждая пара вершин соединена ребром, называется полным.
   Обозначение: U' - граф, состоящий из п вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как w-угольник, в котором проведены все диагонали.
   Определение 5. Степенью вершины называется число ребер, которым принадлежит вершина.
    Обозначение: р (А) - степень вершины А.
  Определение 6. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k.
   Определение 7. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.
    Определение 8. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.
    Определение 9. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.
     Понятия плоского графа и грани графа применяется при решении задач на "правильное" раскрашивание различных карт.
    Определение 10. Путем от А до X называется последовательность ребер, ведущая от А к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.
    Определение 11. Циклом называется путь, в котором совпадают начальная и конечная точка.
    Определение 12. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.
    Определение 13. Длиной пути, проложенного на цикле, называется число ребер этого пути.
    Определение 14. Две вершины А и В в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из А в В.
    Определение 15. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.
    Определение 16. Деревом называется связный граф, не содержащий циклов.
Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское - на поверхности земли.
   Определение 17. Несвязный граф, состоящий исключительно из деревьев, называется лесом.
   Определение 18. Дерево, все п вершин которого имеют номера от 1 до п, называют деревом с перенумерованными вершинами.
Итак, мы рассмотрели основные определения теории графов, без которых было бы   невозможно   доказательство   теорем,   а,   следовательно,   и   решение задач.
Формулировки и доказательства ключевых теорем будут приведены ниже, здесь же объяснены базовые понятия теории.

Закрыть