Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
|
3.4. Способы задания графов В подавляющем большинстве случаев граф задается матрицей. Для расчетов на ЭВМ- B 3 u это единственный способ. Существует редко применяе- D мый сейчас метод задания графа в виде латинской матри- 1 u 4 u цы. В этом способе направление дуг задается порядком 2 u 8 u букв в их названии. Например, рассмотрим граф, изобра- A 9 u женный на рисунке 3.14. Для него латинская матрица E имеет следующий вид. Если граф неориентированный, 6 u 5 u то в латинской матрице просто штрихуют соответствую- C 7 u щую клеточку в таблице. Наиболее часто граф задают с Рис. 3.14. A B C D E A AB AC B BA BD C CA CE D DB E ED EE помощью матриц смежности и инциденций. Рассмотрим изображенный на рисунке 3.14 граф. Как для орграфов, так и для неориентированных графов можно определить матрицу смежности вершин. Это квадратная матрица 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 0 E D C B A E D C B A P n n порядка, где n - число вершин. Ее строки и столбцы соответствуют вершинам графа. Элементы ij p матрицы смежности вершин равны числу дуг, идущих из i - той вершины в j - ю вершину. Если орграф не содержит параллельных дуг, то матрица является бинарной и состоит только из нулей и единиц. В случае неориентированного графа ему вместе с ребром j i x x принадлежит и ребро i j x x , поэтому матрица смежности вершин будет симметрической. Матрица смежности вершин однозначно определяет структуру графа. Теорема 3.4. Графы изоморфны тогда и только тогда, когда их матрицы смежности вершин получаются друг из друга одновременными перестановками строк и столбцов (т. е. одновременно с перестановкой i -й и j -й строк переставляются i -й и j - й столбцы). Доказательство. Рассмотрим два графа G и 1 G , отличающихся лишь нумерацией вершин. Это значит, что в этих графах существует подстановка s на множестве вершин, 56 сохраняющая их смежность: вершины 1 x и 2 x тогда и только тогда смежны в G , когда их образы 1 1 x s y и 2 2 x s y смежны в 1 G . Тогда, если P G P и 1 1 P G P , то n j i p p ij j s i s , 1 , , 1 Из доказанной теоремы следует, что ранги матриц смежности изоморфных графов равны. Это позволяет ввести для графа следующее определение ранга: рангом графа называется ранг его матрицы смежности вершин. Обозначается ранг графа - G rank Аналогично можно определить и матрицу смежности дуг. Это также квадратная матрица m m порядка, где m - число дуг. Рассмотрим тот же граф без петли 9 u . Элементы ij q этой матрицы равны единице, если дуга i u непосредственно предшествует дуге j u и равны нулю в остальных случаях. Для неориентированного графа элемент ij q равен единице, если i u и j u смежны и нулю в остальных случаях. 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 8 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1 u u u u u u u u u u u u u u u u Q Определим для рассматриваемого графа матрицу инциденций. Это прямоугольная матрица размерности m n , где n - число вершин, а m - число дуг. Элементы ij r этой матрицы равны плюс единице, если дуга j u исходит из i -й вершины (начальная вершина), минус единице, если дуга j u входит в i -ю вершину (конечная вершина), нулю, если дуга не инцидентна i -й вершине. В случае неориентированного графа элементами матрицы будут числа единица и нуль, т. е. ребру инцидентна не вершина , 0 , ребру инцидентна вершина , 1 j i j i ij u x u x r Строки матрицы инциденций называют векторами инциденций графа . G Матрица инциденций также одно- 1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 8 7 6 5 4 3 2 1 E D C B A u u u u u u u u R значно определяет структуру графа. Для матрицы инциденций справедлива теорема, аналогичная теореме 3.4. Теорема 3.5. Графы (орграфы) изоморфны тогда и только тогда, когда их матрицы инциденций получаются друг из друга произвольными перестановками строк и столбцов. Простой взвешенный граф (сеть) может быть представлен также своей матрицей весов ij ω , где ij ω - вес ребра, соединяющего вершины i x и j x . Веса несуществующих 57 ребер полагают равными нулю или бесконечности в зависимости от приложений. Очевидно, что матрица весов является простым обобщением матрицы смежности вершин. Определим, теперь, матрицу Кирхгофа . Матрицей Кирхгофа графа G называется матрица n n B , S n , если , , и смежны не и 0, смежны, и , 1 j i x P j i x x x x b i j i j i ij Сумма элементов в каждой строке и каждом столбце этой матрицы равна нулю, т. е. n i ij n j b 1 , 1 , 0 , n j ij n i b 1 , 1 , 0 Кроме того, из этого следует, что алгебраические дополнения всех элементов матрицы B равны между собой. Определим матрицы связности и достижимости. Пусть G P - матрица смежности вершин графа U S G n , , а n P P P E B 2 . Введем матрицу n j i c C ij , 1 , , по правилу 0 если , 0 , 0 если , 1 ij ij ij b b c Матрица C называется матрицей связности, если G - неорграф, и матрицей достижимости, если G - орграф. Это значит, что в графе G тогда и только тогда существует маршрут из вершины i x в вершину j x , когда 1 ij c . Таким образом, в матрице C содержится информация о существовании связей между различными элементами графа G посредством маршрутов. Матрица контрдостижимости n j i l L ij , 1 , , определяется следующим образом: вершины из достижима не вершина если , 0 , вершины из достижима вершина если , 1 j i j i ij x x x x l Можно показать, что C L Матрицы C и L используются для нахождения сильных компонент графа. Пусть L C F * , где операция * означает поэлементное произведение матриц C и L : ij ij ij l c f (см. подразд. 1.2). Элемент ij f матрицы F равен единице тогда и только тогда, когда вершины i x и j x взаимно достижимы, т. е. i x достижима из j x , а j x достижима из i x . Таким образом, сильная компонента орграфа, содержащая вершину i x , состоит из элементов j x , для которых 1 ij f Пример 1. Матрицы достижимости C и контрдостижимости L для графа, изображенного на рис. 3.12, равны Густав Роберт Кирхгоф (1824 – 1887) – немецкий физик. 58 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 P , 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 2 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 2 P , 0 1 0 0 0 0 1 0 0 0 0 0 1 2 1 0 0 0 2 1 0 1 0 0 1 2 0 0 1 0 1 0 0 1 0 0 3 P , 1 0 0 0 0 0 0 1 0 0 0 0 2 2 0 0 1 0 2 3 1 0 0 0 2 1 0 1 0 0 1 2 1 0 0 0 4 P , 0 1 0 0 0 0 1 0 0 0 0 0 2 2 0 1 0 0 3 3 0 0 1 0 2 3 1 0 0 0 2 2 0 0 1 0 5 P , 1 0 0 0 0 0 0 1 0 0 0 0 3 3 1 0 0 0 3 3 0 1 0 0 3 3 0 0 1 0 2 2 0 1 0 0 6 P , 4 3 0 0 0 0 3 4 0 0 0 0 9 10 3 2 2 0 12 13 2 3 2 0 9 10 2 2 3 0 6 7 2 2 3 1 6 5 4 3 2 P P P P P P E B , 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 C , 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 C L , 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 * 6 5 4 3 2 1 6 5 4 3 2 1 x x x x x x x x x x x x L C F . По матрице F легко определить состав вершин трех подграфов, образующих сильно связные компоненты исходного графа. 3.5. Метрические характеристики графа Рассмотрим связный граф U S G , , пусть 1 x и 2 x - две его вершины. Длина кратчайшего 2 1 , x x - маршрута называется расстоянием между вершинами 1 x и 2 x обозначается через 2 1 , x x d . Очевидно, что расстояние между вершинами является простой цепью и 0 , i i x x d . Для любой вершины x величина y x d x e S y , max (3.5.1) называется эксцентриситетом вершины x . Максимальный из всех эксцентриситетов вершин называется диаметром графа и обозначается G d , т. е. y x d x e G d S y S x S x , max max max . (3.5.2) Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через G r : y x d x e G r S y S x S x , max min min . (3.5.3) Вершина x называется периферийной, если ее эксцентриситет равен диаметру графа, 59 т. е. G d x e . Простая цепь, расстояние между концами которой равно G d , называется диаметральной цепью. Теорема 3.6. Для любого связного графа G справедливо неравенство G G d rank . Доказательство. Пусть d G d и 1 2 1 ,..., , d x x x - одна из диаметральных цепей графа G . Рассмотрим матрицу смежности вершин G P и выберем нумерацию вершин так, чтобы вершины 1 2 1 ,..., , d x x x имели номера 1 ,..., 2 , 1 d соответственно. Так как цепь 1 2 1 ,..., , d x x x является подграфом G G / , то D C B A G P представляет собой клеточную матрицу, в левом верхнем углу которой из-за выбранной нумерации вершин расположена матрица смежности подграфа / G Этот подграф является простой цепью, т. е. 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 A симметрическая матрица порядка 1 d , все элементы которой, за исключением двух ближайших к главной диагонали полос, равны нулю. Минор порядка d матрицы A , остающийся после вычеркивания первого столбца и последней строки, равен единице. Следовательно, G d d A G P G rank rank rank , т. е. G d G rank Вершина x называется центральной, если G r x e . Множество всех центральных вершин графа называется его центром. Центром может быть единственная вершина графа или несколько вершин (см. рис. 3.15). Здесь 3 6 4 2 1 x e x e x e x e , 4 7 3 x e x e , 1 x 6 x 2 5 x e . Таким образом, 2 , 4 G r G d . Периферийные 5 x вершины 3 x и 7 x , диаметральные цепи : 7 6 5 2 3 x x x x x и 7 x 7 6 5 2 3 x x x x x , центральная вершина 5 x . 2 x 3 x 4 x Рис. 3.15. |