Наше общество-сложная структура и находить в ней какие-то закономерности-кажется задачей бессмысленной и непостижимой. Но теория графов и статистика позволяет нам находить какие-то удивительные на первый взгляд факты. Но кто этот ваш теория графов- зачем нам изучать графов? И при чём тут дочка Трампа? Обсудим это сегодня.
Вы наверняка видели всякие картинки, где интернет или социальная сеть представляются как какая-то непонятная паутина. Это паутина и называется граф
Граф это который мажор?
Теория графов-это раздел в математике, изучающий какие-то взаимосвязи между объектами посредством графов. Всё ещё непонятно? Это нормально! Граф-это какой-то набор точек и некоторые из них соединены палочкам. Эти точки и палочки называются соответственно вершины и рёбра:
Где же они встречаются в реальной жизни? Ну, к примеру как раз социальные сети, где пользователи- это вершины, а палочки-это знакомства между ними.
Кажется, ну, и нафиг нам эти графы? Но их изучение сильно облегчает нашу жизнь. Например, вам надо доехать до вашего кореша, но вот не задача- он живёт за МКАДом(не пугайтесь). Так вот дороги до него образуют граф, по которому вы и будете добираться. А ваш навигатор ищет наиболее быстрый путь, анализируя этот граф. Из того же разряда-ваш маршрут на метро также анализируется компьютером.
Так, вот теперь уже какой-то рассос, теперь надо немного матеши
Задача о собутыльниках
Допустим, вы вышли во двор, балдежнуть пивка с братвой. Но ваш район весьма популярен, поэтому ваш состав собутыльников постоянно разный. Но обычно в одном дворе пиво пьют только 6 человек. Интересно, всегда ли в компании шести человек найдётся тройка попарно незнакомых людей или тройка попарно знакомых людей? Оказывается, что это всегда да. Но как же так, ведь мы даже не знаем кто там заведомо будет. Вот тут и начинается матеша. Если вам не интересно до-во, проматывайте дальше, но оно вроде легкое.
Допустим все наши ребята-вершины графа. Теперь "раскрасим" наш граф. Если два пацантре знакомы-соединим их синим ребром, если не знакомы, то соответственно красным ребром, как на рисунке:
Тогда задача о тройках сводится к тому: Всегда ли в графе из шести вершин найдётся красный или синий треугольник?. Возьмём произвольно вершину и посмотрим на выходящие из него рёбра. Их 5, так как соседних вершин всего 5, поэтому среди них будет хотя бы 3 синих или 3 красных ребра(иначе рёбер меньше пяти). Допустим у нас есть 3 красных:
Пусть эти красные рёбра соединяют 3 вершины: A,B,C. Тогда Как бы мы соединили эти 3 вершины между собой, у нас образуется синий или красный треугольник(смотри рисунок). Вот мы и доказали!
Задача о мажорах
Допустим на Барвихе поселились 3 мажора. Ну, они уж очень любят гонять в блоу, джипси, маскау сити. Каждый хочет провести по дороге от своего коттеджа до этих мест, но чтоб дорога была прямая. При этом они не хотят, чтобы их дороги пересекались(золотая молодёжь, у них свои капризы). Как же им провести дороги? А вот теория графов говорит, что, блэт, никак! Это называется задача о компланарность графов. Доказательство не лёгкое, поэтому писать его не буду;(
Дочка Трампа
Наверное, вы уже догадались, что это отсылка к треку фейса, где он утверждает, что дочка трампа...
И вот мы задаёмся вопросом, через сколько рукопожатий, дочка Трампа нам... Под рукопожатиями я подразумеваю, цепочку знакомых: условно, друг моего друга, у которого есть друг, и у его знакомого дочка трампа... И сколько нам нужно минимум людей, чтобы такая цепочка построилась. Оказывается, что независимо от того, где ты живёшь, на Колыме или Железноцарске минимум примерно составляет 6 человек!!!
Не уже ли дочка Трампа такая развратница? На самом деле, я не знаю, но теория графов и статистика, утверждает, что
Любых 2 людей на планете, связывает как минимум примерно 6 человек
Это утверждение можно переформулировать в терминах теории графов:
Пусть вершины-это люди, а ребра, как вы уже догадались, знакомство между людьми. Тогда, чтобы дойти от одной вершины до другой, скорее всего вам достаточно пройти по 6 ребрам.
Как видите, теория графов даёт неожиданные результаты!
Надеюсь, вам понравилось, пишите в комментариях тему, о которой вы хотели бы почитать!