Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
Иногда удобно преобразовывать неориентированный граф в ориентированный - заменой каждого неориентированного ребра парой ориентированных ребер с противоположной ориентацией.
На рис.3 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.
Некоторые вершину графа G могут не войти в список пар. Такие вершины называются изолированными. В рассмотренном примере это вершина v6. Граф, у которого все вершины изолированы, называется нуль-графом. Множество ребер такого графа пусто.
Антиподом нуль-графа является полный граф. Ребрами полного графа являются все возможные пары его вершин.
Как в случае ориентированного графа, так и в случае неориентированного, говорят, что ребро инцидентно паре определяющих его вершин.
Одной и той же паре вершин можно поставить в соответствии множество инцидентных ребер. Такие ребра называются кранными. Так, на рис.4 представлены различные пары вершин (vi, vj), инцидентных трем различным ребрам u1, u2, u3. Одно из них направлено, а два - нет.
Рис. 4
Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины. Так, граф приведенный на рис.3, плоским не является, а на рис.4 - плоский.
Если граф G представлен конечным множеством ребер, то он называется конечным, независимо от числа вершин. В противном случае - бесконечный.
Граф Н называется частью графа G или частичным графом Н С G, если множество его вершин V (G) графа G и все ребра U являются ребрами G. Частным, но важным типом частичных графов являются подграфы.
Пусть А - подмножество множества вершин V графа G. Подграф G (A) графа G есть такая часть графа, множеством вершин которого является А, а ребрами - все ребра из G, оба конца которых лежат в А.
Для любой части G графа определена дополнительная часть G (дополнение), состоящая из всех тех ребер, которые не принадлежат G, и всех инцидентных им вершин.
Например, граф G на рис.5 неполный. А проведенные недостающие ребра составляют граф дополнение G рис.6.
Рис. 5Рис. 6
Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Обозначать степени вершин v1, v2, v3 будем так: ? (v1), ? (v2), ? (v3) и т.п.
У графа на рис.7 ? (v1) = 1; ? (v2) = 2. У графа на рис. 8 степени всех вершин равны нулю.
Рис. 7Рис. 8
При решении задач и доказательстве теорем использовались разные способы задания графов. На рисунках граф изображался с помощью точек (крутков, квадратиков) и отрезков, соединяющих пары точек. Можно граф представить специальной таблицей. Пользуются еще матричным представлением графа. Выбирают то представление или способ, который удобнее и нагляднее при рассмотрении конкретного вопроса.
Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер) на бумаге. При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов. Ниже рассматриваются две такие матричные формы и несколько нестандартных представлений, которые наиболее широко используются в алгоритмах на графах.
Пусть имеем граф G (V, U). Его матрицей смежности называется квадратная матрица (аi, j) порядка n2, где n - число вершин, а аi, j - число ребер, инцидентных вершинам vi и vj. Если граф не имеет кратных ребер, то аi, j = 1, когда vi и vj смежные, и аi, j = 0, когда vi и vj не смежные. Если граф не имеет петель, то все его диагональные элементы равны нулю.
Рассмотрим примеры. На рис. 9 изображены три неориентированных графа. В первом случае (рис.9а) имеем граф без петель и без кратных ребер. Во втором случае (рис.9б) имеем кратные ребра. В третьем случае (рис.9в) в вершинах v1 и v4 имеются петли.
абв
Рис. 9
Соответствующие этим трем случаям матрицы смежности представлены ниже:
а) б) в)
Для неориентированного графа матрица смежности является симметрической. Для ориентированного графа матрица смежности симметрической, вообще говоря, не является.
Матрицей инциденций неориентированного графа, называется матрица (bi,j) размера n m, где n - число вершин, а m - число ребер, построенная по правилу
Соответствующие рис.9б матрицы инциденций представлены ниже.
Примечание: для графа на рис. 9б приняты следующие обозначения ребер: Х1 = (v1, v2)1, Х2 = (v1, v2)2, Х3 = (v1, v4)1, Х4 = (v1, v4)2, Х5 = (v1, v4)3, Х6 = (v2, v4), Х7 = (v3, v2).
Матрица инциденций неориентированного графа обладает следующими очевидными свойствами:
) в графе без петель каждый столбец этой матрицы имеет в точности две единицы, соответствующие паре вершин ребра;
) если в графе имеются петли, то в столбцах, соответствующих петлям, имеется по одной единице, а в остальных - по две.
Матрицей инциденций ориентированного графа называется матрица (bi, j) размера n m, где n - число вершин, а m - число ребер, построенная по правилу
Ра