АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Изоморфизм графов.

Часто графы задают изображением их геометрической интерпретации, т.к. этот способ очень нагляден, хоть и не поддаётся формализованному описанию. Вид чертежа зависит от формы линий и взаиморасположения вершин. Иногда не так легко понять, одинаковы ли графы, изображенные разными чертежами.

Пример 6. Одинаковы ли графы?

Очевидно, что и сравнение матриц смежности двух графов не даст ответа на этот вопрос, поскольку вид матрицы зависит от нумерации вершин графа.

Опр.3. Графы, отличающиеся только нумерацией вершин, называется изоморфными. (iso – подобный, morphe – форма).

Перенумерация вершин графа задается строкой d₁, d₂ … d_n новых номеров вершин, стоящих в исходном порядке.

Новая матрица смежности получается из исходной в результате перестановки (d₁, d₂ … d_n) строк и столбцов исходной матрицы.

Чтобы узнать, изоморфны ли графы, представленные матрицами смежности, нужно произвести все возможные перестановки строк и столбцов первой матрицы. Если после одной из таких перестановок возникает матрица, тождественная второй, то значит заданные этими матрицами графы изоморфны. Однако для этого придется выполнить все n! перестановок строк и столбцов.

§ 2.6. Типы графов.

Полный граф. Граф G = (V,E) называется полным, если Е = Е¹² из опр.1 параграфа 3.1. Полный граф порядка n обозначается К_n. Степень вершины любой вершины графа К_n равна n-1.

Пример полного графа: К₆. В нём присутствуют все возможные парные связи между шестью вершинами (т.е. все его вершины смежны).

Орграф G = (X,A) называется полным, если полным является его неориентированный двойник, т.е. если для каждой пары вершин орграфа G существует по крайней мере одна дуга, соединяющая их.

Пустой граф. Граф G = (V,E) называется пустым, если в нём отсутствуют рёбра. Пустой граф порядка n обозначается О_n.

Двудольный граф. Граф G = (V,E) называется двудольным, если множество его вершин Х можно разделить на два подмножества V^a и V^b, таких, что выполняются условия V^a È V^b = V и V^a Ç V^b = Æ, причём у всех рёбер одна концевая вершина лежит в множестве V^a, а вторая – в множестве V^b. Если нужно подчеркнуть, что граф является двудольным, то его обозначают таким образом: G = (Х^а È Х^b, A).

Если в двудольном графе каждая вершина одной доли соединена с каждой вершиной второй доли, а множество вершин разделяется на доли т.о. n₁+n₂=n, то такой двудольный граф называется полным двудольным и обозначается K_n1,n2. Пример двудольного графа: полный двудольный граф К_3,4.

Симметрический граф. Орграф G = (X,A) называется симметрическим, если для каждой его дуги (x_i x_j) в нём присутствует противоположно направленная дуга (x_j x_i).

Антисимметрический граф. Орграф G = (X,A) называется антисимметрическим, если для любой его дуги (x_i,x_j) в нём отсутствует противоположно направленная дуга (x_j,x_i). Очевидно, что в антисимметрическом графе нет петель.

Комбинируя предыдущие определения, можно определить полный симмтрический граф и полный антисимметрический граф. Последний ещё называется турниром.

Симметрический К₃ Антисимметрический К₅ (турнир)

Планарный граф. Если граф G = (V,E) можно изобразить на плоскости или сфере таким образом, что любые две дуги графа не пересекаются друг с другом, такой граф называется планарным.

Примеры непланарных графов (примеры от противного)- графы Куратовского.

a) б)

а – полный граф К₅; б – полный двудольный граф К_3,3. Оба они непланарны, но играют важную роль в теории планарных графов.

Взвешенные графы. Иногда дугам графа G сопоставляются (приписываются) числа – дуге (х_i,х_j) ставится в соответствие некоторое число с_ij, называемое весом, или стоимостью (ценой) дуги. Тогда G называется графом со взвешенными дугами. Иногда веса (числа v_i) приписываются вершинами графа x_i, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то граф называется взвешенным.

§ 2.7. Маршруты и пути.

§ 2.7.1. Маршрут, путь, вес и длина пути.

Опр.4. Пусть G – неориентированный (n,m)-граф, G=(V,E), v_iÎV, e_j Î E.

Чередующаяся последовательность вершин и рёбер графа

v₁, e₁, v₂, e₂,...v_i, e_i, v_i+1,... v_l+1

такая, что e_i =(v_i,v_i+1 ) называется маршрутом, соединяющим v₁ и v_l+1 вершину, или (v₁,v_l+1) маршрутом (обозначается m(v₁,v_l+1)). Иначе говоря, маршрут – это такая последовательность перечисления элементов графа, в которой любые два рядом стоящие элемента инцидентны.

Есть условность индексирования элементов в маршруте. Индексы указывают не истинный номер вершины или ребра в графе, а порядок их перечисления в данном маршруте.

Этот же маршрут можно задать либо последовательностью его вершин v₁,v₂,...v_i, v_i+1,...v_l+1либо рёберe₁,e₂,...e_i,...е_l.

Путём (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой начало каждой последующей дуги является концом предыдущей.

Путь a₁,a₂,...a_i,...a_q называются замкнутыми, если в нём начальная вершина дуги а₁ совпадает с конечной вершиной дуги а_q.

Дата добавления: 2015-09-27 | Просмотры: 844 | Нарушение авторских прав