Теория 10 рукопожатий: «ВКонтакте» запустила приложение для проверки теории шести рукопожатий

Теория шести рукопожатий

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

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

Также присутствовал механизм для отслеживания длины цепочки людей, через которых проходило письмо прежде чем попасть к персоне в целевом городе. Средняя длина цепочки была равна шести.

В 2001 году Дункан Уоттс повторил вышеупомянутый эксперимент на современный манер. В качестве пакета для информации использовались электронные письма. Он получил такой же результат в виде средней длины цепочки равной шести.

Поразительно то, что шесть человек это не так уж и много. Это 0.00000008% от населения земли, которое примерно равно 7,3 миллиарда человек. Шесть человек можно посадить в ладу шестерку и устроить круиз по подмосковью. Но, как ни феноменально, этого может быть достаточно чтобы связать вас с любой, на первый взгляд самой недоступной, персоной.

Графы

Перед тем как мы приступим к рассмотрению возможного объяснения этого феномена нам необходимо познакомится с математическими объектами —

графами, и с некоторыми из их свойств.

Граф это множество вершин и множество ребер, которые соединяют эти вершины. В графическом виде граф можно представить следующим образом:

У нас есть три вершины: A, B, C, и два ребра соединяющие их: AB, BC.

Может кто помнит такой вид развлечения из детства: дают набор точек и путем их правильного соединения получалась картинка какого нибудь котика. Набор точек это множество вершин, и по задаче мы рисовали к ним ребра. Граф в действии. Довольно продвинуто для детей, не находите? Так же я уже описывал такой объект как деревья, которые являются частным случаем графов.

Путь

Как видно из нашего рисунка некоторые ребра непосредственно связаны друг с другом. В нашем предыдущем примере из узла A есть ребро в узел B. Представим все ребра графа как дороги для автомобилей. Ну а там где есть дороги возможно и путешествие! Из A мы можем попасть в B, а из B мы можем попасть в C.

 Следовательно из A мы можем попасть в C, с промежуточной остановке в B.

Такое путешествие, а формально последовательность ребер через которые мы проходим, мы назовем путем. Длину последовательности ребер в пути будем считать длинной пути.

Итак, если мы из A хотим попасть в C, то нам необходимо преодолеть путь (AB, BC). Мы проходим два ребра, следовательно длина пути равна двум.

K-соседи

Для анализа путей вида A → C с промежуточной остановкой в B введем понятие k-соседей.

Вершина B является k-соседом вершине A если:

1. Из вершины А есть путь в вершину B
2. Его длина равна k
3. Это кратчайший путь для двух данных вершин

Рассмотрим пример:

Из узла A в узел C мы можем попасть двумя путями: напрямую через ребро AC, или с промежуточной остановкой в B.  Данные пути, соответственно, мы можем записать следующим образом (AC), (AB, BC). Каким же соседом C является для A? У нас есть два пути, длины этих путей равны 1 и 2 соответственно. Но для того чтобы полностью соответствовать нашему определению нам необходимо выбрать наименее короткий путь, следовательно C является 1-соседом вершине A.

Клика

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

В случае если не все вершины связаны между собой, но какое то подмножество вершин все же полностью связано, то это подмножество называется

кликой графа.

Возьмем, к примеру, следующий граф:

В этом графе вершины A, B, C образуют клику, потому что у нас есть ребра из каждой вершины в каждую, а именно AB, AC, BC.

Сила

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

Приведем пример. В качестве вершин представим города, а в качестве ребер дороги между ними. Это называется дорожной сетью. Почему слово сеть заменило слово граф? Я, поверхностно просмотрев сеть интернет, так и не нашел ответа. Есть некая тенденция сетями называть объекты которые относятся к реальному миру, а графами объекты относящиеся к математическому. А может кому то не нравится благородство происхождения?

Так, не отвлекаемся. Представим себе гипотетическую дорожную сеть между четырьмя городами России:

Изображение схематично, не имеет общего с реальным положением дел

Используя то, что мы уже знаем о графах, проведем вычисления над этим графом. Если мы возьмем Москву как отправную точку нашего путешествия, то Санкт-Петербург, Воронеж, и Ярославль являются 1-соседями Москвы. Архангельск и Волгоград 2-соседями. Также города Москва, Ярославль, Санкт-Петербург образуют клику.

На этом мы не остановимся. Мы, также, можем вычислять кратчайшие пути между городами. Скажем, перед нами стоит задача попасть из Архангельска в Ярославль. Кратчайшим путем будет Архангельск — Санкт-Петербург — Ярославль, а не Архангельск — Санкт-Петербург — Москва — Ярославль.

Еще такой пример. Представим что мы проектируем дорожную сеть. Если на дороге из Москвы в Санкт-Петербург произойдет затор, то мы все же сможем попасть из Москвы в Архангельск через путь Москва — Ярославль — Санкт-Петербург — Архангельск. Но если произойдет затор Москва — Воронеж, то мы не сможем попасть из Воронежа и Волгограда в Санкт-Петербург. Москва является узким местом в нашей дорожной сети. Мы можем это исправить проведя дорогу между Воронежем и Ярославлем.

Звучит довольно тривиально, но переведем наши задачи в масштаб городских улиц. Скажем у нас 3 500 улиц с множеством перекрестков, на каждой из улиц разный параметр загруженности и следовательно время прохождения. Ответ на вопрос «Как быстрее попасть из пункта А в пункт Б» уже не столь тривиален. Сложность выявление узких мест в дорожной сети может стать настоящим кошмаром. Но если мы перекладываем нашу проблему на графы, то мы можем использовать алгоритмы для решения этих задач, а следовательно и компьютеры. Вот это уже звучит более интересно, не так ли?

Решение

Теперь мы полностью готовы рассмотреть наш изначальный вопрос. Для этого мы сконструируем модель социальной сети человечества.

Первое предположение: каждый человек обладает определенным кругом знакомств. У нас есть друзья, и, обычно, каждый наш друг знает другого нашего друга. Таким образом мы формируем некую клику в социальной сети, обозначим ее буквой C.

Второе предположение: у человека есть случайные знакомые не входящие в его круг знакомств. Скажем, с кем то мы учились в школе в параллельных классах или познакомились в детском лагере летом.

Обозначим их буквой R. У каждого из таких случайных знакомых есть своя клика друзей, у людей из этой клики есть свои случайные знакомые и так далее. Скажем у нас есть 12 человек, в каждой клике по 3 человека, у половины по одному случайному знакомому. Социальная сеть будет выглядеть следующим образом:

Давайте посмотрим на k-соседей для A1 в нашей социальной сети. 1-соседи состоят из людей в клике С (вершины B1, C1), и произвольного друга R (вершина A2). 2-соседи состоят из произвольных знакомых людей из нашей клики (CR), и друзей из клики нашего произвольного знакомого (RC). Мы не включаем друзей клики из нашей клики (CC) потому что это теже люди что и сама клика C. В общем случае мы не включаем цепочки в которых C идет два раза подряд. Ну а с 3-соседей довольно затруднительно описать словами, поэтому просто перечислю в виде обозначений: CRR, CRC, RRR, RCR, RRC.

Я знаю вам не терпится это посчитать:

1-соседи:	C + R = 2 + 1 = 3
2-соседи:	CR + RC + RR = 2×1 + 1×2 + 1×0 = 4
3-соседи:	CRR + CRC + RCR + RRC + RRR = 2×1×0 + 2×1×2 + 1×2×0 + 1×0×0 + 1×0×0 = 4

Куча нулей берется потому что наша сеть довольно ограничена, если бы человек было больше размер 3-соседей был бы в разы больше.

Получается что 3 рукопожатия это максимум что нам понадобится для того чтобы войти в контакт с любым человеком из этой сети.

Расширим масштаб нашей сети до 140 человек в клике и 10 случайных знакомых. Посчитаем сколько человек мы можем достать используя 6 рукопожатий:

1-соседи:	C + R = 140 + 10 = 150
2-соседи:	CR + RC + RR = 140×10 + 10×140 + 10×10 = 2 900
3-соседи:	CRR + CRC + RCR + RRC + RRR = 140×10×10 + 140×10×140 + 10×140×10 + 10×10×140 + 10×10×10 = 239 000
4-соседи:	CRRC + CRRR + CRCR + RCRC + RCRR + RRCR + RRRC + RRRR = 6 450 000
5-соседи:	CRRCR + CRRRC + CRRRR + CRCRC + CRCRR + RCRCR + RCRRC + RCRRR + RRCRC + RRCRR + RRRCR + RRRRC + RRRRR = 399 100 000
6-соседи:	CRRCRC + CRRCRR + CRRRCR + CRRRRC + CRRRRR + CRCRCR + CRCRRC + CRCRRR + RCRCRC + RCRCRR + RCRRCR + RCRRRC + RCRRRR + RRCRCR + RRCRRC + RRCRRR = 13 021 000 000

Тринадцать миллиардов. Впечатляет! Это почти в два раза больше чем население земли.

Так откуда возникает столь интересный феномен? Он возникает из структуры нашей сети, а именно из того что у нас есть клики друзей и случайные знакомые. Структура же возникает из того, как каждый элемент сети создает связи с другими элементами. Для объяснения теории шести рукопожатий мы предполагали что у людей есть клика близких знакомых и у каждой такой клики есть связь, некий мост, в другую клику. Вообще, такие графы называются забавным названием «Мир тесен», и что самое удивительное не только социальные сети проявляют свойства подобных графов.

Интересно наблюдать за тем как растет число контактов с ростом числа рукопожатий. Если 1-соседей у нас 150, то 2-соседей уже 2900, а 3-соседей уже 239 000. Это население довольно крупного города. Это может натолкнуть на мысль, что более слабые связи могут дать нам больше, потому что в них участвует большее количество людей. Именно эту идею представляет американский социолог Марк Грановеттер в статье «Сила слабых связей».

Конечно, это не полностью описывает то, как обстоят дела настоящем мире. Это всего лишь игрушечная модель. Но в отличии от анализа реального положения дел, со всеми его деталями, наша модель позволяет нам получить понимание того, почему теория шести рукопожатий имеет место быть.

как работает теория шести рукопожатий

Редагувати переклад

11 декабря 2017, 05:41

От любого человека на Земле нас отделяет лишь шесть рукопожатий – жизнеспособность этой теории изучал Роман Щербаков.

Фото: Thinkstock

Помните, как в романе «Крестный отец» дон Вито Корлеоне поучает горемычного Джонни Фонтейна: «Друзья превыше всего. Дружба важнее таланта. Главнее любого правительства. Она почти то же, что семья, не забывай этого. Если бы ты сумел построить вокруг себя прочную стену дружбы, тебе не пришлось бы прибегать к моей помощи». И действительно – имея необходимые связи, легче устроиться на хорошую работу, да и во всех остальных сферах жизни лишних знакомств не бывает.

Именно об этом говорит знаменитая теория шести рукопожатий. Еще в 1929 году венгерский фантаст Фридьеш Каринти фактически сформулировал ее в рассказе «Звенья цепи», где главный герой хвастался, что может наладить контакт с любым человеком на Земле посредством пяти общих знакомых.

Читайте также: 15 КЛАССИЧЕСКИХ КНИГ И ПОЧЕМУ ИХ СТОИТ ПРОЧЕСТЬ

ВАМ ПИСЬМО

Через 40 лет за дело взялся американский психолог Стэнли Милгрэм. Эксперимент, который он назвал «Мир тесен», заключался в следующем: 300 случайно выбранных людей в маленьком городке на восточном побережье США получили конверты – их следовало переслать через всю страну адресату в Бостоне, с которым они никогда не встречались. Отправлять конверты можно было только через своих знакомых. В итоге цели достигли всего 60 конвертов, но Милгрэм проанализировал данные и сделал вывод, что каждый конверт прошел в среднем через руки пяти человек.

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

Вероятно, какому-то промасленному работяге на заводе Форда стало легче жить, когда он думал, что от знакомства с самим президентом США его отделяет не многоступенчатая кастовая лестница, а шесть простых рукопожатий.

Читайте также: КНИГИ, КОТОРЫЕ ВЫЗЫВАЮТ СИЛЬНЫЕ ЭМОЦИИ

С точки зрения арифметики все более-менее сходится: социологи говорят, что у каждого человека со средними коммуникационными навыками около 300 знакомых. У них тоже примерно 300 приятелей, что расширяет круг общения до 90 тысяч человек. На третьем уровне это уже 27 миллионов, а на четвертом – 8 миллиардов. Но тут важно понимать, что какая-то часть из 300 знакомых вашего знакомого совпадает со списком ваших контактов, и учитывать ее нет смысла.

Не стоит забывать и о том, что в мире до сих пор существуют множество изолированных общин и даже целая сотня народов (например, сентинельцы, проживающие на одном из Андаманских островов), которые враждебно пресекают любые попытки цивилизованного человечества наладить с ними контакт – подойти к аборигенам удается лишь на расстояние выпущенной стрелы. И если дикие племена можно списать на математическую погрешность, то в мире образованных людей по-прежнему существует другая проблема – социальные касты, которые часто становятся непреодолимым барьером, ведь люди склонны общаться в основном с себе равными.

ГЛОБАЛЬНАЯ ДЕРЕВНЯ

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

Идея Милгрэма естественным образом трансформировалась в теорию шести кликов.

Недавно ученые Миланского университета совместно со специалистами Facebook проанализировали связи между 721 миллионом пользователей – их оказалось 69 миллиардов! Согласно исследованию, средняя длина цепочки между двумя незнакомыми людьми в соцсети составляет всего 4,74 «рукопожатия». А если брать только жителей одной страны, то эта цифра будет еще меньше. Новые данные подтвердили мнение о том, что Facebook окончательно превратил мир в глобальную деревню, а эксперимент «Мир тесен» теперь может провести каждый.

Для тех, кому лень самостоятельно выискивать путь к интересному незнакомцу, даже придумали приложение Theory of 6 Handshakes, которое автоматически высчитывает цепочку связей к любому заданному человеку вКонтакте.

Читайте также: Как начать заниматься в спортзале

НА СЛАБО

Разумный подход к теории шести рукопожатий способен кардинально изменить жизнь. Вы можете найти не только работу мечты, но и, например, того симпатичного парня, которого однажды видели в кафе, да так и не решились с ним заговорить. Алекс Рутерфорд из Масдарского института науки и технологий установил: располагая минимальной информацией, можно выйти на любого человека в соцсетях через общих знакомых всего за 12 часов активного поиска. Если же это не удастся, то лишь потому, что люди не до конца осознают возможности своего круга общения.

Поясню: обычно мы рассчитываем только на помощь друзей и родственников – социологи относят их к так называемым «сильным связям». Но близкие люди, как правило, снабжают нас однотипной информацией, что и хорошо, и плохо: наличие сильных связей обеспечивает человеку чувство комфорта и стабильности, но в деле открытия новых жизненных горизонтов оно вряд ли поможет.

Другое дело – слабые связи (соседи, знакомые по спортзалу, случайные попутчики в дальних поездках и так далее). Именно они играют главную роль в поиске контакта с новым человеком. Первые доказательства силы слабых связей были получены еще в 1970-х годах гарвардским социологом Марком Грановеттером. Ученый вывел прямую связь между богатством человека и количеством его слабых социальных связей. А еще он определил, что только 30% безработных в Бостоне устроились на работу благодаря наводкам друзей и родственников. Остальные нашли себе место, узнав о нем от случайных знакомых.

Это объясняется тем, что малознакомые люди вращаются в разных социальных кругах и имеют разные источники информации, что значительно расширяет диапазон поиска. Поэтому для эффективного использования слабых связей важно никогда не забывать о людях, с которыми вы случайно познакомились, например, выгуливая собаку в парке или посещая курсы иностранного языка – рано или поздно те, чье имя вы даже не сразу вспомните, могут сыграть ключевую роль в новом витке вашей жизни.

Чтобы в нужный момент слабые связи «выстрелили», их стоит регулярно подпитывать.

Интересуйтесь, чем живут ваши знакомые – на худой конец, не забывайте просто поздравить их раз в год с днем рождения. Это сущая мелочь, но она даст вам минимальное основание при необходимости обратиться к человеку за помощью. Еще очень важно, чтобы в вашем круге общения были так называемые «люди-шлюзы», объединяющие разные социальные слои – чем больше их будет, тем меньше вероятность, что вы зайдете в тупик на пути к своей цели.

Изучая теорию Стэнли Милгрэма, я вспомнил давнюю мечту – сняться в фильме режиссера Джима Джармуша – и решил составить план последовательных рукопожатий, которые помогли бы мне попасть к мэтру на кастинг. Оказалось, это проще простого! Пару лет назад мне за полцены вырвал зуб тогда еще студент мединститута Борис Горгиев, который однажды выпивал с днепропетровским мастером игры на терменвоксе Артемом Зайцем, который лично знает автора романа «Гопник» Владимира Козлова. У него в друзьях на Facebook есть российский кинокритик Антон Долин, который в прошлом году взял интервью у Джима Джармуша по случаю выхода его последнего фильма «Выживут только любовники».

Получается, до заветной мечты всего пять рукопожатий… Решено: увольняюсь, покупаю книгу Станиславского «Работа актера над собой» и как можно скорее лечу в Голливуд – до встречи на большом экране!

#теории#друзья#знакомства

Статьи по теме

Читайте также

Теория рукопожатий в дискретной математике

следующий → ← предыдущая Мы также можем назвать теорию рукопожатия теоремой о сумме степеней или леммой рукопожатия. Теория рукопожатия утверждает, что сумма степеней всех вершин графа будет удвоена количеством ребер, содержащихся в этом графе. Символическое представление теории рукопожатий описывается следующим образом: Здесь, ‘d’ используется для обозначения степени вершины. ‘v’ используется для обозначения вершины. ‘e’ используется для обозначения ребер. Теорема рукопожатия: В теореме о рукопожатии есть некоторые выводы, которые необходимо сделать, которые описываются следующим образом: На любом графике: Сумма степеней всех вершин должна быть четной. Если степени всех вершин нечетные, то сумма степеней этих вершин всегда должна оставаться четной. Если есть вершины с нечетной степенью, то количество этих вершин будет четным. Примеры теории рукопожатия Существуют различные примеры теории рукопожатия, и некоторые из них описываются следующим образом: Пример 1: Здесь у нас есть граф, степень каждой вершины которого равна 4 и 24 ребра. Теперь узнаем количество вершин в этом графе. Решение: С помощью приведенного выше графика мы получили следующие детали: Степень каждой вершины = 24 Количество ребер = 24 Теперь предположим, что количество вершин = n С помощью теоремы рукопожатия мы имеем следующие вещи: Сумма степеней всех вершин = 2 * количество ребер Теперь мы подставим данные значения в приведенную выше формулу установления связи: н*4 = 2*24 н = 2*6 n = 12 Таким образом, в графе G количество вершин = 12. Пример 2: Здесь у нас есть граф, который имеет 21 ребро, 3 вершины степени 4 и все остальные вершины степени 2. Теперь мы узнаем общее количество вершин в этом графе. Решение: С помощью приведенного выше графика мы получили следующие данные: Количество вершин степени 4 = 3 Количество ребер = 21 Все остальные вершины имеют степень 2 Теперь предположим, что количество вершин = n С помощью теоремы о рукопожатии имеем следующее: Сумма степеней всех вершин = 2 * Количество ребер Теперь мы подставим данные значения в приведенную выше формулу установления связи: 3*4 + (n-3) * 2 = 2*21 12+2n-6 = 42 2н = 42 — 6 2n = 36 n = 18 Таким образом, в графе G общее количество вершин = 18. Пример 3: Здесь у нас есть граф, который имеет 35 ребер, 4 вершины степени 5, 5 вершин степени 4 и 4 вершины степени 3. Теперь найдем количество вершин степени 2 в этом графе. график. Решение: С помощью приведенного выше графика мы получили следующие данные: Количество ребер = 35 Количество вершин степени 5 = 4 Количество вершин степени 4 = 5 Количество вершин степени 3 = 4 Теперь предположим, что количество вершин степени 2 = n С помощью теоремы рукопожатия мы имеем следующие вещи: Сумма степеней всех вершин = 2 * Количество ребер Теперь мы подставим данные значения в приведенную выше формулу установления связи: 4*5 + 5*4 + 4*3 + п*2 = 2*35 20 + 20 + 12 + 2n = 70 52+2n = 70 2н = 70-52 2n = 18 n = 9 Таким образом, в графе G число вершин степени 2 = 9. Пример 4: Здесь у нас есть граф с 24 ребрами, и степень каждой вершины равна k. Теперь узнаем возможное количество вершин из заданных вариантов. 15 20 8 10 Решение: С помощью приведенного выше графика мы получили следующие данные: Количество ребер = 24 Степень каждой вершины = k Теперь предположим, что количество вершин = n С помощью теоремы рукопожатия мы имеем следующие вещи: Сумма степеней всех вершин = 2 * Количество ребер Теперь подставим указанные значения в приведенную выше формулу установления связи: Н*к = 2*24 К = 48/n Обязательно, чтобы целое число содержалось в степени любой вершины. Таким образом, мы можем использовать только те типы значений n в приведенном выше уравнении, которые дают нам целое значение k. Теперь мы проверим приведенные выше параметры, поставив их на место n один за другим, например: При n = 15 мы получим k = 3,2, что не является целым числом. При n = 20 мы получим k = 2,4, что не является целым числом. При n = 8 мы получим k = 6, что является целым числом, и это допустимо. При n = 10 мы получим k = 4,8, что не является целым числом. Таким образом, правильный вариант — вариант С. Следующая темаЗадача Кенигсбергского моста в дискретной математике ← предыдущая следующий →

Теорема о рукопожатии в теории графов | Лемма о рукопожатии

Теорема о рукопожатии-

 

Теорема о рукопожатии также известна как Лемма о квитировании или Теорема о сумме степеней .

 

В теории графов Теорема рукопожатия утверждает в любом заданном графе Сумма степеней всех вершин равна удвоенному количеству ребер, содержащихся в нем.

 

 

Из теоремы о рукопожатии можно сделать следующие выводы.

В любом графе

• Сумма степеней всех вершин всегда четна.
• Сумма степеней всех вершин с нечетной степенью всегда четна.
• Количество вершин с нечетной степенью всегда четное.

Практические задачи, основанные на теореме ручной работы в теории графика-

Проблема-01:

Простой график G имеет 24 края и степень каждого вершины. вершины.

 

Решение-

 

Дано-

• Количество ребер = 24
• Степень каждой вершины = 4

 

Пусть количество вершин в графе = n.

 

Используя теорему рукопожатия, имеем-

Сумма степеней всех вершин = 2 x Количество ребер

 

6

∴ n = 12

 

Таким образом, количество вершин в графе = 12,

 

Задача-02:

 

Граф содержит 21 ребро, 3 вершины степени 4 и все остальные вершины степени 2. Найдите общее количество вершин.

Раствор-

DAD-

• Количество краев = 21
• Количество градуи 4 4 вершины = 3
• Все остальные вершины из градуса 2

. график = n.

 

Используя теорему рукопожатия, мы имеем-

Сумма степеней всех вершин = 2 x Количество ребер

 

Подставляя значения, получаем-

3 x 4 + (n-3) x 2 = 2 x 21

12 + 2n — 6 = 42

2n = 42 — 6

2n = 36

∴ n = 18

Таким образом, общее количество вершин на графике = 18.

Задача-03:

 

Простой граф содержит 35 ребер, четыре вершины степени 5, пять вершин степени 4 и четыре вершины степени 3. Найдите количество вершин степени 2.

Раствор-

DAD-

• Количество краев = 35
• Количество градуля 5 версий = 4
• Количество градуи 4 вершины = 5
• Номер из степени 3 версии = 4
= 4 = 4 = 4.

 

Пусть количество вершин степени 2 в графе = n.

 

Используя теорему рукопожатия, мы имеем-

Сумма степеней всех вершин = 2 x Количество ребер

 

Подставив значения, получим-

4 х 5 + 5 х 4 + 4 х 3 + n х 2 = 2 х 35 70-52

2n = 18

∴ n =

Таким образом, количество градусов 2 вершин на графике = 9.

Проблема-04:

График 240010. и степень каждой вершины равна k, то какое из следующих возможное количество вершин?

1. 20
2. 15
3. 10
4. 8

Раствор-

DAD-

• Количество eDges = 24
• of
  • . вершин в графе = n.

     

    Используя теорему рукопожатия, мы имеем-

    Сумма степеней всех вершин = 2 x Количество ребер

     

    Подставляя значения, мы получаем-

    n x k = 2 x 24

    k = 48 / n

     

    Теперь

    • Очевидно, что степень любой вершины должна быть целым числом.

      No related posts.