Глоссарий

Выберите одно из ключевых слов слева ...

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

Время чтения: ~15 min

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

Вечером, когда гости собираются уходить, все пожимают друг другу руки. Сколько всего рукопожатий?

Мы можем изобразить рукопожатия, используя график: каждый человек - , и каждое рукопожатие .

Теперь легко подсчитать количество ребер в графе. Мы находим, что там с ${hnd} люди есть ${hnd*(hnd-1)/2} рукопожатия.

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

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

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

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

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

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

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

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

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

Archie