Полустепень - исход
Cтраница 3
Отсюда сразу следует, что сумма полустепеней захода всех вершин орграфа D равна сумме их полустепеней исхода, поскольку каждая дуга из D участвует в каждой сумме ровно один раз. [31]
Но это противоречит тому, что в любом орграфе сумма полустепеней захода должна быть равна сумме полустепеней исхода. [32]
 |
Пример орграфа. [33] |
Сумма по столбцу Легко проверить, что суммы элементов по строкам матрицы A ( D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам - полустепеням захода. [34]
У е Y - пару ( Vj, Wj), где соответственно s; и Vj - полустепени исхода, a pt и w - полустепени захода каждой вершины. [35]
В следующем параграфе мы покажем, что из множества графов можно выделить класс графов, имеющих различные пары полустепеней исхода и захода вершин, для которых оценка п при установлении изоморфизма завышена, и приведем верхнюю оценку перебора для графов этого класса. Кроме того, мы сформулируем алгоритм распознавания изоморфизма графов-данного класса и изложим эвристический прием, который в сочетании с приведенным алгоритмом можно применять для распознавания изоморфизма произвольных графов. В § 5 сделана попытка сократить перебор при практическом решении проблемы изоморфного вложения графов и предложен алгоритм распознавания изоморфного вложения графов. Заметим, что указанные алгоритмы распознавания изоморфизма и изоморфного вложения графов удобны для реализации на ЦВМ. [36]
Изобразить все попарно неизоморфные турниры с 5 вершинами, содержащие вершину с нулевой полу степенью захода и вершину с нулевой полустепенью исхода. [37]
В этом параграфе мы уже дали предостаточно определений ( направленный граф, дуга, начальная вершина, конечная вершина, полустепень исхода, полустепень захода, ориентированный путь, простой ориентированный путь, ориентированный цикл, ориентированное дерево, эйлерова цепь, изолированная вершина, свойство быть строго связным, свойство быть деревом с корнем, свойство быть уравновешенным графом), но до сих пор было мало важных результатов, касающихся связи введенных понятий друг с другом. ТеЙерь мы достаточно подготовлены, чтобы разобраться в этом сложном материале. Первым основным результатом является теорема И. [38]
Вершина ориентированного графа называется: а) начальной, если ее полустепень захода равна нулю; б) конечной, или висячей, если ее полустепень исхода равна нулю; в) изолированной, если ее степень равна нулю. Вершины, не являющиеся висячими, называются промежуточными. [39]
Для дальнейшего полезно ввести еще два понятия; источником орграфа D назовем вершину, у которой полустепень захода равна нулю; стоком орграфа D назовем вершину, у которой полустепень исхода равна нулю. Так, на рис. 23.1 вершина v является источником, a w - стоком. Заметим, что эйлеров орграф ( кроме тривиального орграфа, не содержащего дуг) не может иметь ни источников, ни стоков. [40]
 |
I Реберный граф, соответствующий графу, изоб. [41] |
На рис. 36 показан направленный граф, который не только уравновешен, но и регулярен ( или однороден), что означает, что все вершины имеют фдин аковые полустййени захода и одинаковые полустепени исхода. Следовательно, всего имеется ( п 4 - 1) т дуг. [42]
V) есть дерево, в котором полустепень исхода любой вершины равна 2, кроме, быть может, одной вершины, то если в дереве Dl ( V нет вершины с полустепенью исхода 1, то в Dl ( V будет ровно 2 k - 2 ребра, а если в дереве Dl ( V) есть вершина с полустепенью исхода 1, то в Dl ( V ] будет 2 k - 1 ребро. [43]
После того как мы переберем все h, мы получим граф ( переобозначим его через С / з), в котором не будет лишних ребер, т.е. в нем не будет вершин с полустепенью исхода больше 1, причем он по прежнему разрешает ЗИП J, и сложность его после преобразований не увеличилась. [44]
После того как мы переберем все / г, мы получим граф ( переобозначим его через С / з), в котором не будет лишних ребер, т.е. в нем не будет вершин с полустепенью исхода больше 1, причем он по прежнему разрешает ЗИП /, и сложность его после преобразований не увеличилась. [45]
Страницы: 1 2 3 4