Изоморфизм графов.
Часто графы задают изображением их геометрической интерпретации, т.к. этот способ очень нагляден, хоть и не поддаётся формализованному описанию. Вид чертежа зависит от формы линий и взаиморасположения вершин. Иногда не так легко понять, одинаковы ли графы, изображенные разными чертежами.
Пример 6. Одинаковы ли графы?
Очевидно, что и сравнение матриц смежности двух графов не даст ответа на этот вопрос, поскольку вид матрицы зависит от нумерации вершин графа.
Опр.3. Графы, отличающиеся только нумерацией вершин, называется изоморфными. (iso – подобный, morphe – форма).
Перенумерация вершин графа задается строкой d1, d2 … dn новых номеров вершин, стоящих в исходном порядке.
Новая матрица смежности получается из исходной в результате перестановки (d1, d2 … dn) строк и столбцов исходной матрицы.
Чтобы узнать, изоморфны ли графы, представленные матрицами смежности, нужно произвести все возможные перестановки строк и столбцов первой матрицы. Если после одной из таких перестановок возникает матрица, тождественная второй, то значит заданные этими матрицами графы изоморфны. Однако для этого придется выполнить все n! перестановок строк и столбцов.
§ 2.6. Типы графов.
Полный граф. Граф G = (V,E) называется полным, если Е = Е12 из опр.1 параграфа 3.1. Полный граф порядка n обозначается Кn. Степень вершины любой вершины графа Кn равна n-1.
Пример полного графа: К6. В нём присутствуют все возможные парные связи между шестью вершинами (т.е. все его вершины смежны).
Орграф G = (X,A) называется полным, если полным является его неориентированный двойник, т.е. если для каждой пары вершин орграфа G существует по крайней мере одна дуга, соединяющая их.
Пустой граф. Граф G = (V,E) называется пустым, если в нём отсутствуют рёбра. Пустой граф порядка n обозначается Оn.
Двудольный граф. Граф G = (V,E) называется двудольным, если множество его вершин Х можно разделить на два подмножества Va и Vb, таких, что выполняются условия Va È Vb = V и Va Ç Vb = Æ, причём у всех рёбер одна концевая вершина лежит в множестве Va, а вторая – в множестве Vb. Если нужно подчеркнуть, что граф является двудольным, то его обозначают таким образом: G = (Ха È Хb, A).
Если в двудольном графе каждая вершина одной доли соединена с каждой вершиной второй доли, а множество вершин разделяется на доли т.о. n1+n2=n, то такой двудольный граф называется полным двудольным и обозначается Kn1,n2. Пример двудольного графа: полный двудольный граф К3,4.
Симметрический граф. Орграф G = (X,A) называется симметрическим, если для каждой его дуги (xi xj) в нём присутствует противоположно направленная дуга (xj xi).
Антисимметрический граф. Орграф G = (X,A) называется антисимметрическим, если для любой его дуги (xi,xj) в нём отсутствует противоположно направленная дуга (xj,xi). Очевидно, что в антисимметрическом графе нет петель.
Комбинируя предыдущие определения, можно определить полный симмтрический граф и полный антисимметрический граф. Последний ещё называется турниром.
Симметрический К3 Антисимметрический К5 (турнир)
Планарный граф. Если граф G = (V,E) можно изобразить на плоскости или сфере таким образом, что любые две дуги графа не пересекаются друг с другом, такой граф называется планарным.
Примеры непланарных графов (примеры от противного)- графы Куратовского.
a) б)
а – полный граф К5; б – полный двудольный граф К3,3. Оба они непланарны, но играют важную роль в теории планарных графов.
Взвешенные графы. Иногда дугам графа G сопоставляются (приписываются) числа – дуге (хi,хj) ставится в соответствие некоторое число сij, называемое весом, или стоимостью (ценой) дуги. Тогда G называется графом со взвешенными дугами. Иногда веса (числа vi) приписываются вершинами графа xi, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то граф называется взвешенным.
§ 2.7. Маршруты и пути.
§ 2.7.1. Маршрут, путь, вес и длина пути.
Опр.4. Пусть G – неориентированный (n,m)-граф, G=(V,E), viÎV, ej Î E.
Чередующаяся последовательность вершин и рёбер графа
v1, e1, v2, e2,...vi, ei, vi+1,... vl+1
такая, что ei =(vi,vi+1 ) называется маршрутом, соединяющим v1 и vl+1 вершину, или (v1,vl+1) маршрутом (обозначается m(v1,vl+1)). Иначе говоря, маршрут – это такая последовательность перечисления элементов графа, в которой любые два рядом стоящие элемента инцидентны.
Есть условность индексирования элементов в маршруте. Индексы указывают не истинный номер вершины или ребра в графе, а порядок их перечисления в данном маршруте.
Этот же маршрут можно задать либо последовательностью его вершин v1,v2,...vi, vi+1,...vl+1либо рёберe1,e2,...ei,...еl.
Путём (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой начало каждой последующей дуги является концом предыдущей.
Путь a1,a2,...ai,...aq называются замкнутыми, если в нём начальная вершина дуги а1 совпадает с конечной вершиной дуги аq.
Дата добавления: 2015-09-27 | Просмотры: 902 | Нарушение авторских прав
|