Графы. Матричное задание графов. Матрица смежности, матрица инцидентности. Привести примеры.
Граф может быть представлен как в виде рисунка, так и в виде матрицы. Это бывает необходимо при большом числе вершин и дуг (ребер), когда рисунок теряет свою наглядность. Матричное представление графов используется при исследовании его на ЭВМ.
Пусть D = (V, Х) – орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.
Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой
Определение. Матрицей инцидентности орграфа D называется (nґm) –матрица B(D)=[bij], у которой
Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v1,v2, …,vn}, X={x1, x2, …, xm}.
Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой
Определение. Матрицей инцидентности графа G называется (nґm) –матрица B(G)=[bij], у которой
С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Используя матрицу смежности легко определить локальные степени вершин графа: сумма элементов матрицы по строке равна локальной степени соответствующей вершины. Для орграфов по строке определяются полустепени исхода, по столбцам – полустепени захода.
Пример 72.
Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 25).
Решение.
М
атрица
смежности имеет вид
.
Поскольку граф не имеет петель, то на главной диагонали стоят все нули. Для любого графа матрица смежности симметрична относительно главной диагонали.
Д
ля
того, чтобы построить матрицу инцидентности
необходимо пронумеровать ребра графа
(рис. 26). Матрица инцидентности имеет
вид:
Напомним, что в строках указываются вершины, в столбцах – ребра. Матрица инцидентности может быть как квадратной, так и прямоугольной.
Пример 73.
Построить матрицы смежности и инцидентности для орграфа D= (V, X) (рис. 27).
Решение.
М
атрица
смежности имеет вид:
Матрица инцидентности имеет вид
Графы. Маршруты, пути (определение маршрута; начальная, конечная, внутренняя вершины; подмаршрут, выделенный маршрут, выделенный подпуть, длина маршрута, замкнутый маршрут, цепь, простая цепь, цикл (контур), простой цикл (контур)). Привести примеры. Утверждение о выделении просто цикла (простого контура) и простой цепи.
Маршрут в
графе - это последовательность вершин 
,
такая, что для каждого 
вершины 
и 
соединены
ребром. Эти 
ребер
называются ребрами
маршрута.
Говорят, что маршрут проходит через
них, а число
называют длиной маршрута.
Говорят, что маршрут соединяет вершины 
и 
,
они называются соответственно началом и концом маршрута,
вершины 
называются промежуточными.
Маршрут называется замкнутым,
если 
.
Путь - это маршрут, в котором все ребра различны. Путь называется простым, если и все вершины в нем различны.
Цикл -
это замкнутый путь. Цикл 
называется простым,
если все вершины 
попарно
различны.
В графе на рисунке 2.1 последовательность вершин
-
не маршрут;
-
маршрут, но не путь;
-
путь, но не простой;
-
замкнутый маршрут, но не цикл;
-
цикл, но не простой;
-
простой цикл.
Рис. 2.1.
Последовательность ребер графа, в которой любая пара соседних ребер имеет одну и ту же инцидентную вершину, называют маршрутом. В орграфах аналогом маршрута является путь, т.е. такая последовательность дуг, в которой конец одной дуги является началом другой дуги. Маршрут, все ребра которого различны, является цепью, а если различны все вершины, то маршрут — простая цепь. Замкнутая цепь является циклом, замкнутая простая цепь — простым циклом. Цикл, содержащий все ребра графа, называютэйлеровым циклом, а граф, имеющий эйлеров цикл, — графом Эйлера. Простой цикл, который включает все вершины графа, называют гамильтоновым циклом. Для орграфов понятиям цепь и цикл соответствуют понятия путь и контур. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если послед ние заданы).
Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.
Цикл − замкнутая цепь (в неориентированном графе).
Контур − замкнутый путь (в ориентированном графе).
Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.
Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.
Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.
Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.
Длина маршрута (пути) − число ребер в маршруте (дуг в пути).
Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.
Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.