Графики и СетиРукопожатия и знакомства

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

Каждый из ${n} люди на вечеринке пожимают друг другу руки ${n-1} другие. Что делает ${n} × ${n-1} знак равно ${n×(n-1)} Всего рукопожатий. Для русских людей количество рукопожатий будет n×n−1n×n+1n2 ,

К сожалению, этот ответ не совсем правильный. Обратите внимание, как первые две записи в верхнем ряду на самом деле то же самое, просто перевернул.

На самом деле, мы посчитали каждое рукопожатие дважды один раз три раза , один раз для каждого из двух вовлеченных людей. Это означает, что правильное количество рукопожатий для ${n} гости ${n}×${n-1}2=${n*(n-1)/2} ,

Графы рукопожатия являются особыми, потому что каждая вершина связана с любой другой вершиной. Графы с этим свойством называются полными графами . Полный граф с 4 вершинами часто сокращается до K4 , полный граф с 5 вершинами известен как K5 , и так далее.

Мы только что показали, что полный граф с n вершины, Kn имеет n×n−12 кромки.

В другой день вы приглашены на мероприятие по быстрому знакомству для ${m} мальчики и ${f} девушки. Здесь много маленьких столиков, и каждый мальчик проводит по 5 минут с каждой из девочек. Сколько отдельных «дат» в общей сложности?

Двудольный граф с двумя наборами размера x и y часто записывается как Kx,y , Оно имеет x×yx+y2x−y края, Это означает, что в приведенном выше примере есть ${m} × ${f} знак равно ${m×f} даты.