Cтраница 2
Назовем хордовой диаграммой [4] конечный тривалентный планарный граф, состоящий из цикла и неориентированных ребер ( хорд), соединяющих точки на нем. [16]
В ряде случаев естественно рассматривать смешанные графы, имеющие как ориентированные, так и неориентированные ребра. [17]
В ряде случаев приходится рассматривать Смешанные графы, имеющие как ориентированные, так и неориентированные ребра. Семейство пар удобно задавать и в виде матрицы. [18]
В ряде случаев естественно рассматривать смешанные графы, имеющие как ориентированные, так и неориентированные ребра. [19]
Пусть G ( A) содержит цикл С, в котором имеется нечетное число / неориентированных ребер. [20]
Далее орграф можно рассматривать как смешанный граф, заменяя для этого каждую симметричную пару ориентированных ребер неориентированным ребром. [21]
Если матрица инциденций задает граф однозначно, то матрица соседства вершин определяет граф t точностью до замены любого неориентированного ребра парой противоположно направленных дуг между теми же вершинами. Однако для графов без кратных ребер задание графа и этой матрицей однозначно. [22]
Квазилабиринт L назовем деревом, если граф, получающийся из него при замене каждой пары противоположных ребер одним неориентированным ребром, есть дерево. [23]
В этом случае вершины а и Ь должны быть соединены ориентированным ребром в каждом направлении, но проще заменить их одним неориентированным ребром. Таким образом, неориентированные графы отвечают симметрическим отношениям. [24]
Обратно, пусть а е Н, р Н; если ( a, P) - ориентированное ( от а к р) или неориентированное ребро сети S, то ( a, P) e W, если же ( J3, а) - ориентированное ребро сети S, то согласно сказанному выше ( р, a) f W. Очевидно, что в каждой цепи из as в PS найдется ребро, у которого левый конец принадлежит Н, а правый нет. [25]
Такую ориентацию проводить до тех пор, пока в смешанном ИПМ не появится / - ая вершина, для которой v / - р, где у / - число неориентированных ребер, инцидентных этой вершине. Данную / - ую вершину и инцидентные ей выходящие дуги удалить из смешанного ИПМ. [26]
Идея использования выражения 1 2х у состоит в следующем: слагаемое 1 соответствует парам несмежных вершин, в то время как 2х указывает на две возможные ориентации, а у - на неориентированное ребро. Радикал в выражении ( 1 2х z /) 1 / 2 исчезает в тр ( х, у), потому что каждая переменная sk встречается только в четной степени, ибо взаимно обратные циклы обязательно появляются парами. Радикал в 1 г / 1 / 2 также исчезает в тр ( х, у), ибо, как показано в формуле (5.4.5), в единственном ее произведении, содержащем t /, индексы k - четные. Это в свою очередь справедливо потому, что каждый самообратный цикл имеет четную длину. [27]
Идея использования выражения 1 2х У состоит в следующем: слагаемое 1 соответствует парам несмежных вершин, в то время как 2х указывает на две возможные ориентации, а у - на неориентированное ребро. Радикал в 1 У1 / 2 также исчезает в тр ( х, у), ибо, как показано в формуле (5.4.5), в единственном ее произведении, содержащем tk, индексы k - четные. Это в свою очередь справедливо потому, что каждый самообратный цикл имеет четную длину. [28]
Диаграмма DI получается из FDi удалением пометок, петель и объединением пар ребер ( А /) и ( /, А), которые могут существовать в FDi, в одно неориентированное ребро. Очевидно, что число компонент в Di и FDi одно и то же. А /) - и элемент равен пометке на ребре от А к /, если оно существует, и равен О, если такого ребра нет. [29]
Так как каждая такая функция / представляет орграф, скажем, с q ориентированными ребрами и г симметричными парами дуг, то / можно также трактовать как смешанный граф с q ориентированными и г неориентированными ребрами. Очевидно, что любые две функции из множества Fz 21 принадлежат одной и той же орбите степенной группы тогда и только тогда, когда соответствующие им смешанные графы изоморфны. [30]