Доказательство леммы о рукопожатиях

Лемма о рукопожатиях. Число вершин в графе (или мультиграфе без петель), имеющих нечетную степень, четно.

Доказательство леммы. Заметим, что сумма степеней всех вершин в графе (или мультиграфе без петель) должна быть четной. Это следует из того, что если взять вершины, вообще не связанные друг с другом, то сумма степеней этих вершин равна нулю. Прибавляя любое ребро, которое связывает две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна. Удаляя из этой суммы степени четных вершин, получим, что сумма степеней нечетных вершин, должна быть четной. Это значит, что само число таких вершин должно быть четным. Лемма доказана.

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

Графы на рис. 1.3 все выглядят как различные, но каждый из них можно перерисовать так, чтобы он стал (если не обращать внимание на обозначение вершин) идентичен другому. То есть все эти графы в некотором смысле «эквивалентны», имеют одинаковую структуру. Определим более точно характер этой «эквивалентности».

(а) (б) (в) Рис. 1.3. Изоморфные графы

Графы G=(X,U) и G’=(X’,U’) изоморфны (пишут G@G’), если существует взаимно-однозначное соответствие между множествами X и X’, сохраняющее смежность вершин (т.е. такое соответствие, при котором вершины x_i и x_j из множества X смежны тогда и только тогда, когда смежны соответствующие им вершины x’_i и x’_j из множества X’).

Изоморфизм графа рис. 1.3 (а), к графу рис.1.3 (б) обнаруживается, если задать следующее соответствие между вершинами:

а1-б1, а2-б5, а3-б6, а4-б3, а5-б2, а6-б4

(1.1)

Посмотрим, как это делается.

Для рис. 1.3(а) перечень неповторяющихся ребер:

(а1,а4) (а1,а5) (а1,а6) (а2,а4) (а2,а5) (а2,а6) (а3,а4) (а3,а5) (а3,а6)

(1.2)

Для рис. 1.3(б) перечень неповторяющихся ребер:

(б1,б3) (б1,б2) (б1,б4) (б5,б3) (б5,б2) (б5,б4) (б6,б3) (б6,б2) (б6,б4)

(1.3)

Если к (1.2) применить выражение (1.1), то получится выражение (1.3), т.е. графы на рис. 1.3 (а) и рис. 1.3(б) изоморфны.

Установить изоморфизм графа рис. 1.3(в), к графам на рис. 1.3 (а) и рис. 1.3(б) предлагается самостоятельно, определив надлежащее соответствие между их вершинами.

Для рис. 1.3(в) перечень неповторяющихся ребер:

(в1,в2) (в1,в4) (в1,в5) (в3,в2) (в3,в4) (в3,в5) (в6,в2) (в6,в4) (в6,в5)

(1.4)

При сопоставлении выражений (1.2) и (1.4), получается выражение (1.5) устанавливающее изоморфизм графа на рис. 1.3(в), к графу на рис. 1.3 (а):

а1-в1, а2-в3, а3-в6, а4-в2, а5-в4, а6-в5

(1.5)

При сопоставлении выражений (1.3) и (1.4), получается выражение (1.6) устанавливающее изоморфизм графа на рис. 1.3(в), к графу на рис. 1.3 (а):

б1-в1, б2-в4, б3-в2, б4-в5, б5-в3, б6-в6

(1.6)

Дата добавления: 2016-05-16 ; просмотров: 3393 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Степенью (или валентностью) вершины v называется число инцидентных ей ребер. Степень вершины обозначается deg(v). Очевидно, что для любой вершины v V справедливо: 0  deg(v)  |V| –1; deg(v) = |Г(v)|.

Вершина графа, имеющая степень 0, называется изолированной, а вершина со степенью 1 – висячей, или концевой.

Если степени всех вершин графа одинаковы и равны некоторому числу k, то такой граф называется регулярным графом степени k. Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

На рисунке показаны регулярные графы соответственно степени 2 и 3.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а число входящих – полустепенью захода. Эти числа соответственно обозначаются deg – (v) и deg + (v): deg(v)=deg – (v) + deg + (v).

Теорема Эйлера (Лемма "о рукопожатиях"). Сумма степеней всех вершин графа является четным числом и равна удвоенному числу его ребер, т.е. . Для орграфа:.

Действительно, при подсчете данной суммы каждое ребро считается дважды: при определении степени одного конца и при определении степени другого конца.

Последовательность степеней всех вершин графа, записанных в каком-либо порядке, называется степенной последовательностью.

Найдем степенную последовательность для графа G. Выпишем степени всех вершин графа в соответствии с их номерами (2,2,3,2,1).

28) Маршруты, цепи, циклы. Расстояние между вершинами, диаметр графа.

Маршрутом от вершины u к вершине v или (u,v)-маршрутом в графе G называется всякая последовательность вида , в которой любые два соседних элемента инцидентны, т.е.e_k – ребро, соединяющее вершины v_k_–1 и v_k, k = 1,2,…,n.

Это определение подходит также для псевдо-, мульти- и орграфов. В случае орграфа v_k_–1 – начало ребра е_k , a v_k – его конец.

При этом вершину u называют началом маршрута, а вершину v – его концом. В маршруте некоторые вершины и ребра могут совпадать. Если u = v, то маршрут замкнут, а иначе открыт.

Для «обычного» графа маршрут можно задавать только последовательностью вершин или ребер.

Маршрут называется цепью, если в нем нет совпадающих ребер, и простой цепью – если дополнительно нет совпадающих вершин, кроме, может быть, начала и конца цепи. Про цепь u==v говорят, что она соединяет вершины u и v и обозначают u,v.

Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом; замкнутая простая цепь – простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл – контуром.

(1,2,3,4,5,3,2) – маршрут, не являющийся цепью; (1,2,3,4,5,3) – цепь, не являющаяся простой; (1,2,3,4) – простая цепь; (1,2,3,4,5,3,1) – цикл, не являющийся простым; (1,2,3,1) – простой цикл.

Число ребер в маршруте M (возможно, с повторениями) называется его длиной, обозначается |M|.

Расстоянием между вершинами u и v (обозначается d(u,v)) называется длина кратчайшей цепи u,v, а сама кратчайшая цепь называется геодезической.

Если не существует цепи, соединяющей вершины u и v, то по определению d(u,v) = +.

Диаметром графа G (обозначается D(G)) называется длина длиннейшей геодезической.

Максимальным удалением в графе G от вершины v называется r(v) = max d(v,v’),  v’V. Вершина v графа G является его центром, если максимальное удаление от нее до всех вершин принимает наименьшее значение.

Граф, любая из вершин которого является его центром – максимальное удаление до всех вершин от любой =1.

Если какие-либо k юношей знакомы меньше чем с k девушками, то очевидно, их нельзя поженить.

Проведем индукцию по числу юношей.

2. Пусть теорема верна для m-1 юношей.

3. Возможно два следующих варианта:

1) Любые k юношей 1 ≤ k |E(K_n)|=

Билет №29. Выборки и отображения. Три теоремы о числе функциональных отображений.

Пусть — множество всех отображений (функций).

Пусть ;

Тогда

Пусть тогда любое отображениеможно представить в виде упорядоченной последовательности значений функций f в точках из Х, где . Очевидно, что мы тем самым установили взаимнооднозначное соответствие между множеством функциональных отображений и множеством упорядоченных выборок с повторениями объема r из множества y объема n, откуда и следует справедливость доказываемого утверждения. тогда f есть вектор .