Cтраница 2
Ранее было отмечено, что любой граф в абстрактном смысле идентичен, или, используя более принятый термин, изоморфен некоторому геометрическому графу. Изоморфизм графов формально определяется следующим образом: говорят, что графы G ( V, E) и G ( V, Е) изоморфны друг другу, если существует взаимно однозначное соотношение между V и V и между Е и Е, сохраняющее отношения инцидентности. Если граф G изоморфен геометрическому графу G, тогда G называется геометрической реализацией графа G. [16]
Хотя многие графы, представляющие реальные объекты ( после их идеализации), являются геометрическими графами, с точки зрения теории графов их единственная структурная особенность состоит в том, что с каждым геометрическим ребром связаны две ( возможно совпадающие) геометрические вершины. Теория графов построена с учетом именно этой особенности и не учитывает реальной природы вершин и ребер. Таким образом, нумерация ребер и вершин, задаваемая нижеследующей таблицей, содержит всю информацию, необходимую для описания геометрического графа рис. 1.1. Для облегчения общего определения графа введем понятие неупорядоченного произведения множества само на себя. Аналогично, символом ( s & t) будем обозначать неупорядоченную пару элементов множества S, а множество всех различных неупорядоченных пар будет обозначаться как S & S и называться неупорядоченным произведением множества S само на себя. Заметим, что если s имеет k элементов, то S-XS состоит из k2 упорядоченных пар, a S & S - из k ( k l) / 2 различных неупорядоченных пар. Абстрактный граф или просто граф можно определить теперь следующим образом. [17]
Прежде чем определить понятие графа в наиболее общей форме, рассмотрим класс графов, известных под названием геометрических графов. Это позволит с самого начала получить удобное, наглядное предста. Ниже будет показано, что любой граф в абстрактном смысле эквивалентен ( по отношению к свойствам, изучаемым в теории графов) некоторому геометрическому графу. Таким образом, геометрический граф можно рассматривать как удобное представление любых графов, а не просто как частный пример. [18]
Прежде чем определить понятие графа в наиболее общей форме, рассмотрим класс графов, известных под названием геометрических графов. Это позволит с самого начала получить удобное, наглядное предста. Ниже будет показано, что любой граф в абстрактном смысле эквивалентен ( по отношению к свойствам, изучаемым в теории графов) некоторому геометрическому графу. Таким образом, геометрический граф можно рассматривать как удобное представление любых графов, а не просто как частный пример. [19]