Терминология теории простых графов

Question

Я только начинаю изучать основы теории графов, и мой учебник немного неясен относительно простой концепции.Термин «смежность», насколько я понимаю, учитывая ненаправленный граф, если узлы A и B соединены, A смежна с B, а B смежна с A. Мне было интересно, было ли это все еще верно, учитывая направленный граф, гдеА указывает на B?

Спасибо

Answer 1

Похоже, это было довольно хорошо объяснено, но для обеспечения некоторых визуальных эффектов. Смежные ребра - это два соединенных узла, и есть две основные настройки:

В неориентированном графе два узла A и B, соединенные ребром, смежны друг с другом

В ориентированном графе два узла A и B, соединенные ребром от A до B, означают, что вы можете добраться до B из A (или B рядом с A):

Answer 2

В орграфе есть ребро от v1 до v2, тогда v2 смежно с v1. (От v1 до v2, как в v2 - голова, а v1 - хвост.)

В неориентированном графе это симметрично - если v2 смежно с v1, тогда v1 также смежно с v2, и мы говорим v1 ~ v2.

В орграфе v1 не обязательно также может быть смежным с v2, поэтому мы говорим v1 ↓ v2.

РЕДАКТИРОВАТЬ: также вы могли бы попытаться задать такой вопрос на сайте CSTheory Stackexchange в будущем - вы можете получить лучшие ответы.

Answer 3

В ориентированном графе, где A указывает на B, {A,B} будет включено в список смежности графа, а {B,A} не будет.То есть A смежна с B, но не наоборот.