Ориентированные и неориентированные графы.

Граф, в котором направление линий не выделя­ется (все линии являются ребрами), называется неориентирован­ным;

Граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.

Из ориентированного графа сделать неориентированный граф – убрать стрелки

12. Способы задания графов: аналитический, геометрический, матричный. Матрицы смежности и инцидентности графа. Маршруты, циклы и цепи графа.

1. Геометрический способ задания графа – ну, просто нарисовать его таким, какой он есть.

2. Матрицей смежности – берем две вершины. Если между ними есть дуга или ребро – то пишем 1, нет – 0.

3. Матрица инцидентности – берем вершину. Если из нее выходит дуга - пишем 1, входит - -1, нет – 0.

Матрицу инцидентности можно построить для ориентированных и неориентированных графов.

Вершина, соединенная с ребром – инцидентна.

Две вершины соединенные ребром – смежные.

Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1, v2 - вершины, а e = (v1, v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

Маршрут в графе — это чередующаяся последовательность вершин и рёбер v₀, e₁, v₁, e₂, v₂, …, e_k, v_k, в которой любые два соседних элемента инцидентны. Если v₀ = v_k, то маршрут замкнут, иначе открыт.

Маршрут, в котором ребра не повторяются – цепь (путь). Длина пути для ориентированного графа – количество дуг (ребер).

Цепи, у которых начала и концы совпадают – циклы.

Связность графов.

Связный граф – из любой вершины есть маршрут в другую (матрица связности для такого графа состоит из единиц только)

матрица связности – в ней 0 и 1

1 – из одной вершины есть маршрут в другую

0 – нет маршрута.

Эйлеровы графы.

Граф Эйлера – в котором существует цикл.

Эйлеров граф – в нем есть маршрут, проходящий через все дуги по одному разу.

Цикл - это путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

Не нашли, что искали? Воспользуйтесь поиском: