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

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

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

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

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


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

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

Графы G=(X,U) и G’=(X’,U’) изоморфны (пишут G@G’), если существует взаимно-однозначное соответствие между множествами X и X’, сохраняющее смежность вершин (т.е. такое соответствие, при котором вершины xi и xj из множества 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 называется всякая последовательность вида , в которой любые два соседних элемента инцидентны, т.е.ek – ребро, соединяющее вершины vk–1 и vk, k = 1,2,…,n.

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

При этом вершину 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’),  vV. Вершина v графа G является его центром, если максимальное удаление от нее до всех вершин принимает наименьшее значение.

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

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

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

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

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

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

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

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

Пусть ;

Тогда

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

Пусть ;

Тогда число всех инъективных отношений из x в y равно .

Пусть , тогда любой инъекции соответствует вектор ;

Пусть , тогда число всех биекций равно n!

  • АлтГТУ 419
  • АлтГУ 113
  • АмПГУ 296
  • АГТУ 266
  • БИТТУ 794
  • БГТУ «Военмех» 1191
  • БГМУ 171
  • БГТУ 602
  • БГУ 153
  • БГУИР 391
  • БелГУТ 4908
  • БГЭУ 962
  • БНТУ 1070
  • БТЭУ ПК 689
  • БрГУ 179
  • ВНТУ 119
  • ВГУЭС 426
  • ВлГУ 645
  • ВМедА 611
  • ВолгГТУ 235
  • ВНУ им. Даля 166
  • ВЗФЭИ 245
  • ВятГСХА 101
  • ВятГГУ 139
  • ВятГУ 559
  • ГГДСК 171
  • ГомГМК 501
  • ГГМУ 1966
  • ГГТУ им. Сухого 4467
  • ГГУ им. Скорины 1590
  • ГМА им. Макарова 299
  • ДГПУ 159
  • ДальГАУ 279
  • ДВГГУ 134
  • ДВГМУ 408
  • ДВГТУ 936
  • ДВГУПС 305
  • ДВФУ 949
  • ДонГТУ 497
  • ДИТМ МНТУ 109
  • ИвГМА 488
  • ИГХТУ 130
  • ИжГТУ 143
  • КемГППК 171
  • КемГУ 507
  • КГМТУ 269
  • КировАТ 147
  • КГКСЭП 407
  • КГТА им. Дегтярева 174
  • КнАГТУ 2909
  • КрасГАУ 345
  • КрасГМУ 629
  • КГПУ им. Астафьева 133
  • КГТУ (СФУ) 567
  • КГТЭИ (СФУ) 112
  • КПК №2 177
  • КубГТУ 138
  • КубГУ 107
  • КузГПА 182
  • КузГТУ 789
  • МГТУ им. Носова 367
  • МГЭУ им. Сахарова 232
  • МГЭК 249
  • МГПУ 165
  • МАИ 144
  • МАДИ 151
  • МГИУ 1179
  • МГОУ 121
  • МГСУ 330
  • МГУ 273
  • МГУКИ 101
  • МГУПИ 225
  • МГУПС (МИИТ) 636
  • МГУТУ 122
  • МТУСИ 179
  • ХАИ 656
  • ТПУ 454
  • НИУ МЭИ 640
  • НМСУ «Горный» 1701
  • ХПИ 1534
  • НТУУ «КПИ» 212
  • НУК им. Макарова 542
  • НВ 778
  • НГАВТ 362
  • НГАУ 411
  • НГАСУ 817
  • НГМУ 665
  • НГПУ 214
  • НГТУ 4610
  • НГУ 1992
  • НГУЭУ 499
  • НИИ 201
  • ОмГТУ 301
  • ОмГУПС 230
  • СПбПК №4 115
  • ПГУПС 2489
  • ПГПУ им. Короленко 296
  • ПНТУ им. Кондратюка 119
  • РАНХиГС 186
  • РОАТ МИИТ 608
  • РТА 243
  • РГГМУ 117
  • РГПУ им. Герцена 123
  • РГППУ 142
  • РГСУ 162
  • «МАТИ» — РГТУ 121
  • РГУНиГ 260
  • РЭУ им. Плеханова 122
  • РГАТУ им. Соловьёва 219
  • РязГМУ 125
  • РГРТУ 666
  • СамГТУ 130
  • СПбГАСУ 315
  • ИНЖЭКОН 328
  • СПбГИПСР 136
  • СПбГЛТУ им. Кирова 227
  • СПбГМТУ 143
  • СПбГПМУ 146
  • СПбГПУ 1598
  • СПбГТИ (ТУ) 292
  • СПбГТУРП 235
  • СПбГУ 577
  • ГУАП 524
  • СПбГУНиПТ 291
  • СПбГУПТД 438
  • СПбГУСЭ 226
  • СПбГУТ 193
  • СПГУТД 151
  • СПбГУЭФ 145
  • СПбГЭТУ «ЛЭТИ» 379
  • ПИМаш 247
  • НИУ ИТМО 531
  • СГТУ им. Гагарина 113
  • СахГУ 278
  • СЗТУ 484
  • СибАГС 249
  • СибГАУ 462
  • СибГИУ 1654
  • СибГТУ 946
  • СГУПС 1473
  • СибГУТИ 2083
  • СибУПК 377
  • СФУ 2423
  • СНАУ 567
  • СумГУ 768
  • ТРТУ 149
  • ТОГУ 551
  • ТГЭУ 325
  • ТГУ (Томск) 276
  • ТГПУ 181
  • ТулГУ 553
  • УкрГАЖТ 234
  • УлГТУ 536
  • УИПКПРО 123
  • УрГПУ 195
  • УГТУ-УПИ 758
  • УГНТУ 570
  • УГТУ 134
  • ХГАЭП 138
  • ХГАФК 110
  • ХНАГХ 407
  • ХНУВД 512
  • ХНУ им. Каразина 305
  • ХНУРЭ 324
  • ХНЭУ 495
  • ЦПУ 157
  • ЧитГУ 220
  • ЮУрГУ 306
Читайте также:  Не работает клавиатура на планшете dexp

Полный список ВУЗов

Чтобы распечатать файл, скачайте его (в формате Word).

Ссылка на основную публикацию
Для чего нужна калибровка стиральной машины
Страница 41 калибровка стиральной машины _41 05 КАЛИБРОВКА С калибровка стиральной машины Стиральная машина Samsung автоматически определяет вес белья. Для...
Вытяжка bosch замена ламп
Страница 9 Информация для предварительного ознакомления. Официальной информацией изготовителя не является. Отключите вытяжку от электросети, длячего выньте вилку из розетки...
Где находится кнопка page up на клавиатуре
Не каждый пользователь знает, для чего нужны все клавиши на клавиатуре для ПК. Но среди них много нужных и не...
Доказательство леммы о рукопожатиях
Лемма о рукопожатиях. Число вершин в графе (или мультиграфе без петель), имеющих нечетную степень, четно. Доказательство леммы. Заметим, что сумма...
Adblock detector