Часть графа называется подграфом графа
Если , а подмножество образовано только ребрами, инцидентными вершинам множества Е’.
Полным графом называется граф , у которого каждая вер-
Рис. 1.9. Полный граф |
шина соединена ребрами с остальными вершинами (рис. 1.9).
Маршрутом графа G называется последовательность ребер S = = (u1, u2, … un), в которой каждые два соседних ребра имеют общую вершину, т.е. Не исключено,
Что одно и то же ребро может встречаться несколько раз на одном маршруте.
Две вершины е1 и е. называются связанными, если существует маршрут из еi в е.j
Компонентой связности графа называется подмножество его вершин с инцидентными им ребрами, такое, что любая вершина связана с любой другой вершиной маршрута, Например, из графа на рис. 1.10 можно выделить следующие две компоненты связанности, показанные сплошной линией.
Рис. 1.10. Компоненты связанности графа
Простой цепью, или простым путем, называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следующий граф имеет цикл S = (1, 2, 3, 5, 4, 1) (рис. 1.11).
Рис. 1.11. Цикл в графе
Цикл, проходящий по всем ребрам графа только один раз, называется эйлеровым циклом. В теории графов доказывается теорема, определяющая, содержит ли граф эйлеров цикл. Оказывается, конечный граф содержит эйлеров цикл тогда и только тогда, когда он связан, и все его локальные степени вершин четные. Важной прикладной задачей теории графов является задача поиска в графе цикла, проходящего через каждую вершину только один раз. Такие циклы называются гамильтоновыми циклами.
Весьма важным является связанный граф, не имеющий циклов, он называется деревом. В дереве любые две вершины связаны единственным путем. Вершина называется концевой, если ей инцидентно не более одного ребра; одна из концевых вершин может быть выбрана в качестве корня.
Задание графа
Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Аналитическое задание состоит в задании элементов множества вершин и множества ребер
Для выполнения различного рода формальных преобразований над графами удобно использовать -их матричные задания. Матрица А размерностью n х n называется матрицей смежности графа ,
если ее элементы образованы по правилу: элемент матрицы если вершины еi. и еj. соединены m ребрами, и
, если эти вершины не связаны ребрами. Матрица смежности имеет число строк и столбцов, равное количеству вершин графа.
Матрица А размерностью n х m называется матрицей инцидентности графа G(Е,U),если ее элементы образованы по правилу: элемент матрицы . если вершина е. инцидентна ребру
в противном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента.
Построим матрицы смежности и инцидентности для графа, изображенного на рис. 1.12.
Рис. 1.12. Пример графа Матрица смежности будет состоять из пяти строк и пяти столбцов.
Статьи к прочтению:
Сломаная рука! ►Dead By DayLight◄+ любые ыгри многий стрим
Похожие статьи:
-
Алгоритм граф путь работоспособность
Введение Определение достижимости населенного пункта в системе односторонних дорог рассматривается при помощи некоторого математического объекта,…
-
Решение задач 103—115 из учебника
Задача 103. Задача на понимание нового листа определений. Если вы видите, что кто-то выписывает цепочки, которые путями дерева D не являются, попросите…