Неориентированная графа
Cтраница 2
В этом случае вершины а и Ь должны быть соединены ориентированным ребром в каждом направлении, но проще заменить их одним неориентированным ребром. Таким образом, неориентированные графы отвечают симметрическим отношениям. [16]
Нлвание транспортная сеть является данью интерпретации в связи с транспортной задачей. Обычно подобные объекты называют неориентированными графами. [17]
& f связанные с матрицей смежноотей графа G, будем называть обыкновенными. Здесь термян граф используется в более широка, смысле, т.е. в случаях, не вызывающих недоразумений, будем обозначать этим термином неориентированные графы, орграфы, мультиграфы и щглыгиорграфы. [18]
Поскольку орграф планарен тогда и только тогда, когда планарен соответствующий неориентированный граф, полученный игнорированием направления ребер, то достаточно рассматривать только неориентированные графы. Поскольку неориентированный граф планарен тогда и только тогда, когда все его связные компоненты планарны, достаточно рассматривать лишь связные неориентированные графы. Более того, легко видеть, что неориентированный граф планарен тогда и только тогда, когда все его двусвязные компоненты планарны. Поэтому, если неориентированный граф является разделимым, мы можем разложить его на двусвязные компоненты и рассматривать их отдельно. Наконец, поскольку параллельные ребра и петли всегда можно добавить к графу или удалить из него без нарушения свойства планарности, достаточно рассматривать только простые графы. [19]
Таким образом, получаем матрицу смежности ( вершин) M ( G), которая полностью описывает G, если граф имеет однократные ребра. Если G - неориентированный граф, то ребра ( а / с, а /) и ( а, Ok) существуют одновременно. Таким образом, неориентированным графам соответствуют симметричные матрицы смежности. [20]
Какие фактические значения и переменные отражены в отношениях и Т - зависимостях, не имеет значения при проверке того, удовлетворяет ли отношение Т - зависимости. Важны лишь равенства между значениями и между переменными. Мы будем пользоваться неориентированными графами для представления отношений и Т - зависимостей: при этом, как и следовало ожидать, вершины будут соответствовать кортежам и строкам, а помеченные ребра между вершинами будут указывать атрибуты, на которых кортежи или строки совпадают. [21]
В этих задачах от Вас требуется сравнить два остовных дерева или два пути. Такое сравнение провести легче, если обозначать ребра парой вершин в порядке возрастания их меток. Это возможно, поскольку работать придется с неориентированными графами. [22]
Поскольку орграф планарен тогда и только тогда, когда планарен соответствующий неориентированный граф, полученный игнорированием направления ребер, то достаточно рассматривать только неориентированные графы. Поскольку неориентированный граф планарен тогда и только тогда, когда все его связные компоненты планарны, достаточно рассматривать лишь связные неориентированные графы. Более того, легко видеть, что неориентированный граф планарен тогда и только тогда, когда все его двусвязные компоненты планарны. Поэтому, если неориентированный граф является разделимым, мы можем разложить его на двусвязные компоненты и рассматривать их отдельно. Наконец, поскольку параллельные ребра и петли всегда можно добавить к графу или удалить из него без нарушения свойства планарности, достаточно рассматривать только простые графы. [23]
 |
Задача для графа С4. [24] |
Рассмотрим 8 классов графов с отмеченными вершинами. Каждый из этих классов определяется заданием параметров а, р4 и у. При этом, если а 0, то рассматриваются графы без петель, если же а1, то петли допускаются; если ( 3 0, то рассматриваются графы без параллельных ребер, если р 1, то параллельные ребра допускаются; если 7 0, то рассматриваются неориентированные графы, если у1, то вводится ориентация ребер. [25]
В клетках матрицы, расположенных по главной диагонали, находятся нули, так как граф не имеет петель. Вследствие того, что рассматриваются неориентированные графы, будем оперировать только с треугольной матрицей. Единицы матрицы смежности, соответствующие ребрам га-мильтонова цикла, заменим крестиками, а единицы, соответствующие ребрам графа Gn вне гамильтонова цикла, заменим черточками. Оставшиеся единицы в клетках матрицы Rn соответствуют ребрам внутри гамильтонова цикла. Кроме того, заметим, что ребра, находящиеся внутри выпуклой фигуры, можно расположить во внешней области, а внешние - во внутренней. [26]
Ориентированные графы будут обозначаться через D, ( V, А, А) или через ( V, А), когда А не задано в явном виде. Таким образом, граф G получается из графа D отбрасыванием требования упорядоченности граничных точек каждой дуги. Структурные термины, введенные в главе 1, применимы также и к ориентированным графам. При их описании необходимо использовать соответствующие неориентированные графы. [27]
При обходе в глубину проход по выбранному пути осуществляется настолько глубоко, насколько это возможно, а при обходе по уровням мы равномерно двигаемся вдоль всех возможных направлений. Изучим теперь эти два способа более подробно. В обоих случаях мы выбираем одну из вершин графа в качестве отправной точки. Ниже под посещением узла мы понимаем выполнение действия, которое необходимо совершить в каждой вершине. Если, например, идет поиск, то фраза о том, что мы посетили данный узел, означает, что мы проверили его на наличие требуемой информации. Описываемые методы работают без каких-либо изменений как на ориентированных, так и на неориентированных графах. [28]
Страницы: 1 2