C#. Орграфы. Теория.

Теория графов, университет ИТМО

Орграф – множество вершин и коллекция ориентированных ребер.

Полустепень исхода

Полустепень входа

Ориентированный путь орграфа – последовательность вершин, в которой существует ориентированное ребро, указывающее из каждой вершины на след. вершину этой последовательности.

Ориентированный цикл – ориентированный путь, содержащий как минимум 1 ребро, в котором 1 и последняя вершины совпадают.

Длина пути цикла – количество ребер в нем.

Простой цикл – без повторяющихся ребер и вершин (кроме обязательного совпадения 1 и последней вершины)

Достижимость из v  в w, если существует ориентированный путь из v в w.

Представление ориентированного графа в файле

Представление орграфа списками смежности

Разница в представлении с неориентированными графами. Для неориентированных графов, если v находится в списке смежности вершины w, то и w находится в списке смежности вершины v. Однако, в представлении списками смежности для орграфов такой симметрии нет. Каждое ребро присутствует в списке смежности только один раз.

Достижимость и связность

Можно легко сказать связаны ли вершины v и w, но сложно сказать, можно ли достичь вершины w из v.

This entry was posted in C#. Bookmark the permalink.

Leave a Reply