Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




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

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

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

 

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

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

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

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

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

 

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

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

 

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

 

Маршрут в графе — это чередующаяся последовательность вершин и рёбер v0, e1, v1, e2, v2, …, ek, vk, в которой любые два соседних элемента инцидентны. Если v0 = vk, то маршрут замкнут, иначе открыт.

 

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

 

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

 

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

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

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

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

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

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

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

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

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




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

vikidalka.ru - 2015-2019 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных