Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

являются команды. Пара команд А и В связывается ребром каждый раз, когда они сыграли. Если А выиграла у В, то это ребро будем ориентировать от А к В. а если В выиграла у А, то противоположном направлении; в случае ничьей ребро будет неориентированным.

Для каждого графа G существует обратный граф G^*, получаемый изменением ориентации каждого из ребер G на противоположную. Для

каждого ориентированного графа существует также соотнесенный неориентированный граф G_u, ребрами которого являются ребра G, но уже без ориентаций. Иногда удобно превратить неориентированный граф G в ориентированный граф G_d при помощи процесса удвоения, состоящего в замене каждого ребра G парой с теми же концами и приписывании им противоположных ориентаций.

Граф называется плоским, если он может быть изображен на плоскости так что все пересечения ребер являются вершинами G. Граф на рис 1.8а плоский, а на рис 1.8б неплоский.

§2. Матрицы смежности и инцидентности.

В §1 мы определили ребро Е (1.2) графа G (1.1) как элемент или точку (a, b) в произведении VV. Как обычно, элементы этого произведения можно представить в виде клеток квадратной таблицы М с элементами множества V в качестве координат по двум осям (рис 2.1).

В точку с координатами (a, b) поместим числа 1 или 0 в зависимости от того, существует или не существует в G соответствующее ребро. Таким образом, мы получили конечную или бесконечную матрицу смежности (вершин) М(G), которая полностью описывает G, если имеет однократные ребра. Обычно обозначения выбираются так, чтобы элементы (а, а), соответствующие петлям, располагались на главной диагонали матрицы М. Если G–неориентированный граф, то ребра (a, b) и (b, a) существуют одновременно, таким образом, неориентированным графам соответствуют симметрические матрицы смежности.

Если G имеет кратные ребра, то числа 0 и 1 в клетках (a, b) можно заменить кратностями (a, b) ребер, соединяющих а и b. Это дает описание графа G матрицей с целыми неориентированными элементами. Обратно, любая такая матрица может быть интерпретирована как граф, так что любые результаты для графов могут быть сформулированы как свойства таких матриц.

Сказанное приводит к дальнейшему расширению понятия графа, использующему уже все конечные или бесконечные матрицы, элементами которых являются вещественные неотрицательные числа. Такие матрицы встречаются в различных областях математики. Например, стохастические матрицы – в теории вероятностей и в теоретической физике. Где рассматриваемая система имеет некоторое множество V возможных состояний, и любая пара состояний (a , b) связывается некоторой вероятностью перехода (a, b). Другим примером является граф, представляющий схему дорог, в котором (a, b) означает соответствующее расстояние между а и b.

Графы могут быть также описаны матрицами другого вида. Всякий граф состоит из объектов двух типов–вершин и ребер. Можно построить матицу M₁(G), строки которой соответствуют вершинам, а столбцы–ребрам. На месте (а, Е) в этой матрице поместим значение =1, если а–начальная вершина ребра Е, значение =-1, если а–конечная вершина, и =0, если а не инцидентно Е. Если G–неориентированный граф, то можно использовать только значения =1 и =0. Эта матрица M₁(G) называется матрицей инцидентности графа G.

Введем, наконец, матрицу смежности ребер I(G), в которой и строки и столбцы отвечают ребрам G. Для простоты предположим. Что G не имеет петель, а ребра неориентированные и однократные. На месте (E, E’) в I(G) поместим =1, если Е и Е’–различные ребра с общим концом, и =0, если Е=Е’ или если они не имеют общего конца. Таким образом, I(G)–квадратная матрица, определяемая графом G.

Можно встать и на другую точку зрения и рассматривать I(G) как матрицу смежности вершин для нового графа, также обозначаемого через I(G), вершинами которого являются ребра Е графа G, а ребрами–пары (E, E’) с =1. Назовем I(G) графом смежности ребер или смежности графом для G. Существование такого графа, в котором бывшие ребра становятся вершинами и наоборот, объясняет двойственность между вершинами и ребрами, встречающуюся в некоторых вопросах теории графов.

Фактическое построение смежности графа I(G) по чертежу графа G просто. На каждом ребре Е выбираем фиксированную точку е_Е, например середину Е. Пару таких вершин (е, е’) соединяем новым ребром, принадлежащим I(G), тогда и только тогда, когда соответствующие ребра Е и Е’ имеют общую вершину в G.

Рис. 2.2 дает это построение для графа тетраэдра; смежностным графом для него является граф октаэдра.

Предположим, то в вершине е сходится (е) ребер Е=(е, е’) из G. Тогда в I(G) середина e_E ребра Е соединяется ребрами с (е)–1 серединами остальных ребер из G, имеющих конец в е. Таким образом, в I(G) эти новые ребра образуют новый граф U(e) с (е) вершинами. В I(G) вершина e_E соединяется ребрами также с (е’)–1 серединами остальных ребер из G, из имеющих конец в e’, и эти новые ребра образуют другой полный граф U(e’). Два графа U(e) и U(e’) имеют ровно одну общую вершину, именно вершину e_E, определяемую единственным ребром Е, соединяющим e и e’. Таким образом, I(G) имеет такое непересекающееся по ребрам разложение

I(G)= 2.1

На полные графы U(e) с (е) вершинами, что U(e) имеет единственную общую вершину с каждым из (е) других полных графов U(e’). Исключение составляет случай, когда (e, e’)–единственное ребро в e’, т.е. (е’)=1. Тогда не существует графа. U(e’).

Предположим, что, наоборот, для графа G₁ существует такое разложение (2.1) на полные графы, что пара (U(e), U(e’)) имеет не более одной общей вершины. Тогда G₁ можно рассматривать как смежностный граф G₁=I(G) некоторого графа G, считая, что каждое U(e) имеет ₁ (е) общих вершин с другими U(e’). Каждому U(e) поставим в соответствие одну вершину e и соединим e и e’ ребром в G тогда и только тогда, когда U(e) и U(e’) имеют общую вершину. К этим ребрам добавим (е)– ₁ ребер (e, e’’), идущих к новым вершинам e’’, в которых существует только одно это ребро.

§3 Деревья

Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим (или) лесом. Таким образом, компонентами леса являются деревья. На рис.12 изображены все деревья шестого порядка.

Существует несколько вариантов определения дерева; некоторые из них отражены в следующей теореме.

Теорема 3.1 Для графа следующие утверждения эквивалентны:

1. G – дерево;

2. G – связный граф и m=n-1;

3. G – ациклический граф и m=n-1;

4. любые две несовпадающие вершины графа соединяет единственная простая цепь;

5. G – ациклический граф, обладающий тем свойством, что если каку–либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

1) 2) Воспользуемся индукцией по n. При n=1 утверждение трививально. Пусть n>1, е EG. В дереве G нет циклов, следовательно, согласно лемме 4.1, граф G – е имеет ровно две компоненты Т₁ и Т₂,

каждая из которых есть дерево. Пусть дерево T_i является (n_i, m_i) – графом, i=1, 2. По индуктивному предположению верно равенство

m_i=n_i-1. (1)

Далее имеем

m=m₁+m₂+1=(n₁-1)+(n₂-1)+1=(n₁+n₂)-1=n-1.

2) 3) Граф G связен и m=n-1. Нужно доказать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть ребро е–ребро этого цикла. Тогда граф G – е связен (лемма 4.8) и имеет n-2 ребра, что противоречит теореме 4.9. следовадельно, G –ациклический граф.

3) 4) Пусть к–число компонент графа G. Пусть, далее, компонента Т_i является (n_i, m_i)–графом. Так как Т_i–дерево, то верно равенство (1). Теперь имеем

n-1=m=m₁+m₂+…+m_k=(n₁-1)+(n₂-1)+…+(n_k-1)=(n₁+…+n_k)-k=n-k;

т.е. к=1. Итак, G–связный граф и потому любые несовпадающие вершины u и v соединены в нем просой цепью. Если бы в G были две несовпадающие простые (u,v)–цепи, то согласно утверждению 4.3 их объединение содержало бы цикл. Следовательно, каждые две вершины соединены единственной простой цепью.

4) 5) пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей мере двумя простыми цепами. Следовательно, граф G ациклический. Пусть u и v–две его нечмежные вершины. Присоединим к графу G ребро e=uv. В G есть простая (u,v)–цепь, которая в G+e дополняется до цикла. В силу утверждения 4.4 этот цикл единственный.

5) 1) нужно докакзать, что граф G связен. Если бы вершины u и v принадлежали разным компонентам графа G, то граф G+uv не имел бы циклов,что потиворечит утверждению 5). Итак, G связен и потому является деревом. Доказано.

Следствие 3.2. В любом дереве порядка n2 имеется неменее двух концевых вершин.

Пусть

d₁, d₂, …, d_n (2)

–степенная последовательность дерева. Тогда

Характеристики

Список файлов реферата