Cтраница 1
Геометрический граф, изоморфный данному графу. [1]
Геометрический граф в пространстве е есть множество V - v точек пространства е и множество Е е простых кривых, удовлетворяющих следующим условиям. [2]
Рассматривая геометрический граф, можно зафиксировать некоторую вершину и, последовательно двигаясь по смежным ребрам к вершинам, прийти в другую вершину или вернуться в исходную. В геометрическом графе это означает, что мы непрерывным образом двигаемся по последовательности простых кривых. Последовательности ребер, по которым можно двигаться непрерывным образом, играют фундаментальную роль в теории графов. [3]
Граф, изоморфный геометрическому графу на плоскости. [4]
В настоящем параграфе мы рассмотрим понятие графа ь узком смысле, а именно понятие так называемого геометрического графа. [5]
Прежде чем определить понятие графа в наиболее общей форме, рассмотрим класс графов, известных под названием геометрических графов. Это позволит с самого начала получить удобное, наглядное предста. Ниже будет показано, что любой граф в абстрактном смысле эквивалентен ( по отношению к свойствам, изучаемым в теории графов) некоторому геометрическому графу. Таким образом, геометрический граф можно рассматривать как удобное представление любых графов, а не просто как частный пример. [6]
Ранее было отмечено, что любой граф в абстрактном смысле идентичен, или, используя более принятый термин, изоморфен некоторому геометрическому графу. Изоморфизм графов формально определяется следующим образом: говорят, что графы G ( V, E) и G ( V, Е) изоморфны друг другу, если существует взаимно однозначное соотношение между V и V и между Е и Е, сохраняющее отношения инцидентности. Если граф G изоморфен геометрическому графу G, тогда G называется геометрической реализацией графа G. [7]
Чтобы получить возможность четкого описания различных структурных свойств графов, полезно ввести ряд дополнительных понятий, которые особенно наглядно иллюстрируются на примере геометрических графов. [8]
Рассмотрим геометрический граф G ( V, Е) в пространстве е2, где V состоит из всех точек с координатами ( к, у), х0 или 1 и О г / 1, и в котором для каждого у вершины ( О, у) и ( 1, у) соединяются ребром, представляющим собой отрезок прямой. Если рассмотреть G как точечное множество, то это просто единичный квадрат в е2, который является односвязным. Однако как граф, он в сильной степени не связен, так как вершина ( 0, у) соединяется цепью только с вершиной ( 1, у) и ни с какой другой. [9]
Множество ребер, которые, будучи соответственно упорядоченными, образуют цепь. В геометрическом графе это множество ребер, которые образуют незамкнутую кривую. [10]
Множество ребер, которые, будучи соответственно упорядоченными, образуют цикл. В геометрическом графе это множество ребер, которые образуют замкнутую кривую. [11]
Множество дуг, которые будучи соответственно упорядоченными, образуют контур. В геометрическом графе это замкнутая кривая, образованная соответственно ориентированными дугами. [12]
Рассматривая геометрический граф, можно зафиксировать некоторую вершину и, последовательно двигаясь по смежным ребрам к вершинам, прийти в другую вершину или вернуться в исходную. В геометрическом графе это означает, что мы непрерывным образом двигаемся по последовательности простых кривых. Последовательности ребер, по которым можно двигаться непрерывным образом, играют фундаментальную роль в теории графов. [13]
Во многих случаях ребрам графа необходимо задать ориентацию или направление. Применительно к геометрическому графу ориентацию можно интерпретировать как направление передвижения по ребру. В случае же абстрактного графа задание направления означает, что граничные точки каждого ребра отличаются упорядочением. [14]
Если v0vn, но все остальные вершины различны, то последовательность ребер называется простым циклом, а соответствующее неупорядоченное множество ребер - неупорядоченным простым циклом. Заметим, что в геометрическом графе простые цепи образуют простые незамкнутые кривые ( см. определение выше), а простые циклы - простые замкнутые кривые. [15]