English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtГрафики и СетиГрафики в повседневной жизни
Мы видели много разных применений теории графов в предыдущих главах, хотя некоторые из них были немного надуманными. Оказывается, однако, что графики лежат в основе многих объектов, концепций и процессов в повседневной жизни.
Например, Интернет - это огромный виртуальный граф. Каждая вершина является отдельной веб-страницей, и каждое ребро означает, что между двумя страницами есть гиперссылка. Обратите внимание, что ссылки идут только в одну сторону, поэтому этот график
Некоторые веб-сайты, такие как Википедия или Facebook, имеют много входящих ссылок, в то время как многие меньшие сайты могут иметь очень мало входящих ссылок. Это основная концепция, которую Google использует для сортировки результатов поиска.
Сайты с большим количеством входящих ссылок, как правило, более высокого качества и должны отображаться в верхней части результатов поиска. Например, при поиске «Лондон» официальные туристические информационные сайты показываются перед небольшими магазинами в Лондоне или блогами людей, которые живут в Лондоне. Эта простая идея из теории графов, алгоритм Page Rank , сделала Google значительно лучше, чем другие ранние поисковые системы.
Интернет - самая большая сеть, когда-либо созданная человечеством. Это изображение показывает очень небольшую долю всех серверов, подключенных к Интернету:
Хотя веб-сайты и гиперссылки образуют виртуальный график, существует также физическая сеть компьютеров, серверов, маршрутизаторов, телефонных линий и кабелей.
Каждый раз, когда вы звоните по телефону или загружаете веб-сайт, операторы сети должны найти способ подключения отправителя и получателя, не превышая пропускную способность любого отдельного кабеля или соединения. Теория графов и вероятность позволяют гарантировать надежное обслуживание, например, путем обнаружения отклонений, когда определенное соединение занято.
Графики также играют важную роль в транспортировке и навигации. Все сети рейсов, поездов и метро образуют графики, которые можно использовать при создании эффективных расписаний. Один из самых узнаваемых графиков - карта лондонского метро:
Все дороги и автомагистрали также образуют большую сеть, которая используется навигационными службами, такими как Google Maps, при разработке кратчайшего маршрута между двумя указанными точками.
В будущем интеллектуальные транспортные системы сократят заторы и несчастные случаи благодаря более эффективной маршрутизации автомобилей, используя данные о местоположении, полученные со смартфонов и автомобилей с самостоятельным вождением. Это может сэкономить миллионы часов, потерянных на дороге каждый год, значительно снизить загрязнение и позволить аварийным службам быстрее путешествовать.
На этом изображении показана сеть рейсов коммерческих авиакомпаний по всей Северной Европе.
Есть множество других графиков в науке, технике или повседневной жизни:
Связи между атомами в молекулах и кристаллических решетках образуют график.
Распространение болезней и эпидемий можно смоделировать с помощью сети.
В биологии эволюционные деревья, которые показывают происхождение видов, образуют график.
Различные компоненты электрических цепей и компьютерных чипов образуют сеть.
Грамматическая структура языков может быть смоделирована с использованием графиков, например, для создания алгоритмов перевода.
Графы также имеют много приложений в области вероятности , теории игр и финансовой математики .
Социальные сети
Наконец, давайте подумаем об одном особенно хорошем примере графиков, которые существуют в повседневной жизни: социальные сети. Здесь вершины представляют
Когда мы рисуем графики в социальных сетях, мы можем видеть определенные группы общих друзей, которые, возможно, учились в одной школе или живут в одном городе. Мы также можем определить центральность людей , которая зависит от того, насколько хорошо связана вершина, и которая может быть мерой популярности человека в социальных сетях.
В 2014 году у Facebook было 1,4 миллиарда активных пользователей и более 200 миллиардов друзей. Половина всех пользователей Facebook имеет более 200 друзей, а поскольку у большинства наших друзей такое же количество друзей, у нас легко могут быть десятки тысяч друзей друзей .
Теперь волнующим вопросом будет: если вы выберете двух случайных пользователей Facebook, сколько «дружеских сторон» вам понадобится, чтобы перейти от одного к другому? Например, расстояние между друзьями равно
В 2016 году Facebook провел исследование, чтобы определить, как его пользователи связаны друг с другом. Они обнаружили, что в среднем вы подключены к кому-либо еще на Facebook через не более 3,57 других людей. И это включает в себя знаменитостей, политиков или даже роялти!
Другими словами, если вы выберете любого из миллиардов пользователей Facebook по всему миру, у них, вероятно, будет друг друга, который знает друга одного из ваших друзей. Мы говорим, что есть 3,57 степени разделения .
Geographic visualisation of all Facebook friendships in 2010.
В 1929 году, когда венгерский писатель
В 1967 году
Сегодня каждый из нас является частью бесчисленных невидимых графиков, которые лежат в основе наших социальных взаимодействий, путешествий, Интернета и технологий, науки и многого другого.