Граф и его элементы
Граф — это математическая модель объектов и связей между ними. В информатике графами описывают дороги между городами, соединения компьютеров, маршруты транспорта и отношения между объектами; в этой теме разберём, что такое вершины и рёбра, как находить степень вершины и как задавать граф.
Что такое граф
Граф обозначают \(G=(V,E)\), где \(V\) — множество вершин, а \(E\) — множество рёбер. Вершины изображают точками или кружками, рёбра — линиями между ними. Например, вершины могут обозначать города, а ребро — дорогу между двумя городами.
Граф — это совокупность вершин и соединяющих их рёбер. Вершина графа — отдельный объект модели, а ребро графа — связь между двумя вершинами.
Если ребро соединяет вершины \(A\) и \(B\), говорят, что оно инцидентно этим вершинам. Подробнее об этом свойстве см. инцидентность. Вершины \(A\) и \(B\) при наличии общего ребра называются смежными вершинами.
Степень вершины
Степень вершины показывает, сколько рёбер выходит из этой вершины или входит в неё. Она обозначается \(\deg(v)\) или \(d(v)\). Чтобы найти степень, достаточно пересчитать рёбра, инцидентные данной вершине.
Степень вершины — число рёбер, инцидентных этой вершине. В неориентированном графе каждое обычное ребро увеличивает степень каждой из двух своих вершин на единицу.
Сумма степеней всех вершин неориентированного графа равна удвоенному числу его рёбер: каждое ребро посчитано дважды — по одному разу у каждого конца.
Вершина степени \(0\) называется изолированной: она не соединена ни с одной другой вершиной. Вершина степени \(1\) называется концевой. Петля, то есть ребро из вершины в неё же, в стандартном подсчёте увеличивает степень вершины на \(2\).
В графе четыре вершины и пять рёбер. Чему равна сумма степеней всех вершин?
Как задают граф
В задачах граф может быть дан рисунком, таблицей, списком пар вершин или матрицей. Важно сначала определить, что обозначают вершины и рёбра, а затем выбрать удобный способ подсчёта.
- Рисунок графа. Вершины показаны точками, рёбра — линиями. Нужно внимательно пересчитать все соединения.
- Список рёбер. Каждая пара, например \((A,B)\), означает ребро между \(A\) и \(B\). Повторять одну и ту же пару в простом графе нельзя.
- Матрица смежности. Строки и столбцы соответствуют вершинам. Единица на пересечении строки \(A\) и столбца \(B\) означает наличие ребра \(A-B\), ноль — отсутствие.
- Список смежности. Для каждой вершины перечисляют все вершины, соединённые с ней.
Для неориентированного графа матрица смежности симметрична относительно главной диагонали: если \(A\) соединена с \(B\), то и \(B\) соединена с \(A\). Сумма элементов строки матрицы равна степени соответствующей вершины.
| Вершина | Смежные вершины | Степень |
|---|---|---|
| A | B, C | 2 |
| B | A, C, D | 3 |
| C | A, B, D | 3 |
| D | B, C | 2 |
В таблице или матрице сначала найдите, что считается вершиной. Затем для нужной вершины посчитайте единицы в её строке или соседей в списке. Не смешивайте число вершин с числом рёбер.
Разобранный пример
Дан неориентированный граф с вершинами \(A,B,C,D,E\). Его рёбра: \(AB\), \(AC\), \(BC\), \(BD\), \(CD\), \(DE\). Найдите степени всех вершин и проверьте результат правилом суммы степеней.
Ответ: \(\deg(A)=2\), \(\deg(B)=3\), \(\deg(C)=3\), \(\deg(D)=3\), \(\deg(E)=1\). Проверка сошлась, значит, ни одно ребро не пропущено и не посчитано лишний раз.
Простые и ориентированные графы
В школьных задачах по умолчанию часто рассматривают простой неориентированный граф: в нём нет петель и кратных рёбер, а связь между двумя вершинами не имеет направления. Если направление важно, используют ориентированный граф. Например, дуга \(A\to B\) может означать дорогу только из \(A\) в \(B\).
В ориентированном графе отдельно считают полустепень исхода — число дуг, выходящих из вершины, и полустепень захода — число дуг, входящих в неё. Если рёбрам приписаны длины, цены или пропускные способности, граф называют взвешенным графом. Такие понятия понадобятся при изучении маршрутов в графе.
1. Считать вершины вместо рёбер при нахождении степени. 2. Забывать одно из рёбер, если оно пересекается с другим на рисунке: пересечение линий не считается вершиной без специальной точки. 3. Для неориентированного графа считать \(AB\) и \(BA\) разными рёбрами. 4. Использовать правило \(\sum\deg(v)=2|E|\) для ориентированного графа без разделения входящих и исходящих дуг.
Что нужно знать к заданиям
- Определите множество вершин и множество рёбер.
- Если дан рисунок, проверьте, где находятся настоящие вершины; простое пересечение линий вершиной не является.
- Для степени конкретной вершины выпишите все инцидентные рёбра и пересчитайте их.
- Для проверки используйте формулу суммы степеней.
- Если граф задан матрицей, сложите элементы нужной строки; если списком рёбер — посчитайте пары с нужной вершиной.
Проверь себя
Главное
- Граф состоит из множества вершин \(V\) и множества рёбер \(E\): \(G=(V,E)\).
- Степень вершины — число инцидентных ей рёбер; сумма степеней равна \(2|E|\).
- Граф задают рисунком, списком рёбер, списком смежности или матрицей смежности.
- В матрице смежности степень вершины равна сумме элементов её строки.
- При решении сначала различите вершины и рёбра, затем пересчитайте связи и выполните проверку формулой.