Теория:
Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в управлении производством, бизнесе, при построении путей транспортировки и доставки, решении задач.
Графы используют в связи с развитием теории вероятности, математической логики и информационных технологий.
Граф — это конечная совокупность вершин, некоторые из которых соединены ребрами, т.е. это совокупность точек, называемых вершинами, и линий, соединяющих некоторые из вершин, называемых ребрами или дугами в зависимости от вида графа.
Пример:
Мультиграф — это граф, у которого пара вершин соединены несколькими ребрами. А такие ребра, которые соединяют одну и ту же пару вершин, называют кратными. Две различные вершины графа, соединенные ребром, называются смежными.
Петля — это ребро, которое соединяет вершину саму с собой.
На рисунке 1 изображен мультиграф со смежными ребрами (выделены черным цветом), кратными ребрами (выделены красным) и петлями (выделены синим).
Степенью вершины называют количество ребер, выходящих из одной вершины. Для петли ребро выходит из вершины дважды. Обозначать степень вершины \(а\) будем как .
Пример:
На рисунке 2 изображен граф с 7 вершинами.
Рис. 2
Составим список степеней вершин этого графа:
Свойства графов:
- В любом графе есть, по крайней мере, две вершины, имеющие одинаковую степень.
- Для любого графа количество вершин нечетной степени всегда будет четное.
- Сумма степеней всех вершин графа равна удвоенному числу его ребер.
Маршрут на графике — это последовательность ребер , в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.
Рис. 2
Цепь — это маршрут, в котором каждое ребро содержится не более одного раза. Цепь, являющаяся циклическим маршрутом, называется циклом.
Для графа, изображенном на рисунка 2, — цепь, — цикл.
Цепь называется простой, если проходит через каждую свою вершину ровно один раз. Цикл называется простым, если является простой цепью.
Для графа, изображенном на рисунка 2, — простая цепь, — простой цикл.
Связанные вершины — это вершины \(a\) и \(b\), для которых существует цепь, начинающаяся в \(a\) и заканчивающаяся в \(b\).
Связный граф — это граф, у которого любые две вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом).
Один и тот же граф может быть изображен по-разному. Например, граф на рисунке 2 тот же, что и изображен на рисунке 3.
Рис. 3
Источники:
Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. - Москва: Просвещение, 2012. -219 с.