Условие:
Задан ориентированный граф с помощью списка ребер.
задать граф c помощью диаграммы, матрицы инцидентности, матрицы смежности;
выписать для графа следующие несовпадающие друг с другом последовательности (по одной каждого вида): маршрут, путь, простой путь, контур, простой контур.
преобразовать граф в неориентированный граф и задать его с помощью диаграммы, матрицы инцидентности, матрицы смежности;
выписать для графа следующие несовпадающие друг с другом последовательности (по одной каждого вида): маршрут, цепь, простая цепь, цикл, простой цикл.
проверить, является ли граф эйлеровым, и если является, то найти остов, выписать хорды и записать матрицу фундаментальных циклов.
,
Решение
Задаем граф c помощью диаграммы:
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
матрицы инцидентности:
матрицы смежности:
выпишем для графа следующие несовпадающие друг с другом последовательности (по одной каждого вида):
маршрут (последовательность вершин, соединенных ребрами) – v1, v5, v6
путь (маршрут без повторяющихся дуг) - v1, v5, v6;
простой путь (путь с различными вершинами), – v1, v5, v6;
контур (циклический путь) – отсутствует;
простой контур (контур с различными вершинами) - отсутствует.
преобразуем граф в неориентированный граф и задаем его с помощью диаграммы:
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
матрицы инцидентности:
матрицы смежности:
выпишем для графа следующие несовпадающие друг с другом последовательности (по одной каждого вида): маршрут, цепь, простая цепь, цикл, простой цикл.
маршрут (последовательность вершин, соединенных ребрами) – v2, v3, v8, v2, v4, v1, v2, v3;
цепь (маршрут без повторяющихся дуг) – v3, v2, v8, v6, v5, v1, v2;
простая цепь (цепь с различными вершинами), – v3, v2, v8, v6, v5;
цикл (циклическая цепь) – v2, v8, v3, v2, v1, v4, v2;
простой цикл (цикл с различными вершинами) – v1, v6, v5, v1.
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
проверим, является ли граф эйлеровым:
Граф называется эйлеровым, если он имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу - эйлеровый цикл.
Граф связный (каждая его вершина связана со всеми другими) и степени всех его вершин четные, что является необходимым и достаточным условием того, что он эйлеровый.
Эйлеровый цикл: v1, v2, v3, v8, v2, v4, v1, v5, v6, v7, v8, v6, v1.
Остов графа (связный частичный граф данного связного графа, содержащий все вершины графа, но не содержащий циклов):
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
v1
v2
v3
v4
v5
v7
v8
v6
e11
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e12
Хорды графа (ребра, на входящие в остов): e6, e7, e8, e9, e12.
Фундаментальные циклы (цикл, состоящий из хорды и тех ветвей остова, которые соединяют концы хорды простой цепью):
,
,
,
,
.
Матрица фундаментальных циклов:
Задать вопрос
на новый заказ в Автор24.
