Обработка неориентированных графов как подкатегории ориентированных графов

10

Грубо говоря, неориентированный граф очень похож на ориентированный граф, где для каждого ребра (v, w) всегда есть ребро (w, v). Это говорит о том, что было бы приемлемо рассматривать неориентированные графы как подмножество ориентированных графов (возможно, с дополнительным ограничением, что добавление / удаление ребер может быть сделано только в совпадающих парах).

Тем не менее, учебники обычно не следуют этому подходу и предпочитают определять неориентированные графы как отдельную концепцию, а не подкатегорию ориентированных графов. Есть ли причина для этого?

graphs terminology Максимум
источник
2
Обратите внимание, что существуют также «смешанные графы»: граф, где ребра могут быть направлены или нет. В этом случае пара направленных ребер не совпадает с неориентированным ребром между двумя узлами. Например: рассмотрим улицы: у вас может быть пара улиц с односторонним движением между двумя точками, идущими в противоположных направлениях, или одна улица с двусторонним движением. Это важно в некоторых случаях: например, вы не хотите, чтобы навигационное устройство сообщало пользователю о необходимости разворота между двумя улицами с односторонним движением, если в середине есть барьер, хотя это может быть возможно сделать в одна улица с двусторонним движением.
Бакуриу

Ответы:

8

Вы абсолютно правы; это совершенно правильный способ просмотра неориентированных графиков.

Иногда в неориентированных графах некоторые вещи становятся проще и понятнее. Например, вам не нужно беспокоиться о разнице между слабосвязанными и сильно связанными компонентами в неориентированных графах. Алгоритмы для неориентированных графов иногда могут быть более эффективными или более простыми, чем если бы мы применяли соответствующий алгоритм для ориентированных графов.

Итак: возможно, некоторые учебники предпочитают следовать этой трактовке, поскольку она позволяет им сначала представить проблему в (более простом) контексте неориентированных графов, а затем обобщить до (более сложного) случая ориентированных графов. Это просто предположение.

DW
источник
3

На этой странице приведены примеры проблем, для которых форма неориентированного графа на самом деле сложнее, чем форма ориентированного графа. К ним относятся, например, поиск цикла с отрицательным весом и подсчет числа эйлеровых циклов. Мне кажется, что эти проблемы кажутся сложнее в неориентированных графах, потому что часть задачи может быть сформулирована как-то, выбирая правильное «направление» для каждого ребра - что, конечно, «уже сделано для нас», когда граф направлен.

j_random_hacker
источник
1
О верно. Например, цикл Эйлера, когда он определяется в терминах ориентированных графов, должен был бы потребовать, чтобы «из каждой пары (v, w), (w, v) использовалось не более одного ребра») - создавая идею представления неориентированного графа как орграф менее привлекательный.
максимум
0

Трудно мотивировать что-то очень общее неожиданно; это может сделать доказательства и учебники более простыми, но не обязательно более легкими для понимания и интуитивно понятными.
Люди обычно находят более интуитивным выучить простую концепцию, а затем обобщить ее до чего-то более абстрактного, вместо того, чтобы определять какую-то суперобобщенную и абстрактную концепцию, а затем создавать экземпляры ее конкретных случаев. Это, наверное, один из тех случаев.

user541686
источник