Теория графов от Эйлера до социальных сетей

программирования
Огнева М.В.

математику и инженеру Маринони от 13 марта 1736 года.

В

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

росчерком пера, не проводя дважды ни одну линию?

цепей
Множество фундаментальных циклов в графе

языке графов: найти число всех деревьев с заданным количеством вершин

и со степенями вершин 1 и 4

«вокруг света» по ребрам многогранника, посещая каждую вершину ровно один

раз

должен посетить N городов, побывав в каждом из них ровно по одному

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

три общих колодца. Можно ли провести непересекающиеся дорожки от каждого

дома к каждому колодцу?

задача о домиках и колодцах не имеет решения на плоскости

(приблизительно) Ф.Гатри постановка задачи: «сколько потребуется красок для раскраски любой

плоской карты таким образом, чтобы никакие две смежные области не были окрашены в один и тот же цвет»
Гипотеза: достаточно четырех красок

британский математик Альфред Брей Кемпе дал ошибочное доказательство
1890 г. лектор

Дурхэмского университета Перси Джон Хивуд опровергнул доказательство Кемпе и показал, что гипотеза верна для пяти красок
1925 г. Филипп Франклин, оставив в стороне общую проблему четырех красок, сумел доказать, что для раскрашивания любой карты, содержащей не более 25 областей, требуются только четыре краски.
1940 г. Винн распространил доказательство на карты с 35 областями
1970 г. Оре и Стемпл увеличили число областей до 39

журнала «Scientific American» Мартин Гарднер опубликовал карту, для раскрашивания которой

якобы требовались пять красок.

Задача о раскраске карт или гипотеза о четырех красках

Аппель, предложили новый метод, перевернувший традиционные представления о математическом доказательстве.
Хакену

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

Задача о раскраске карт или гипотеза о четырех красках

ребра – наличие авиарейса
Вершины – люди, ребра - отношение «знакомы

между собой»
Вершины – спортсмены, ребра – отношение «играли между собой»

вершины зависит от сказанных данным персонажем слов
Ребра - диалоги персонажей;

толщина ребра зависит от количества состоявшихся разговоров.

почти 2 миллиона слов.
Для сбора данных было привлечено машинное обучение (точность

определения принадлежности разговора составляет около 75%).

(расстояние между наиболее удаленными вершинами графа) равен 8
Поиск путей:

77 персонажей находятся «в центре» графа, иными словами они могут связаться с любым другим персонажем не более чем через 4х других

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

направленных от A к B, сколько есть ссылок с сайта A на сайт B, и столько ребер, направленных от B к A, сколько есть ссылок с сайта B на сайт A. 

разреженным: если вершин у веб-графа n, то ребер у него не более mn с некоторым

постоянным m ≥ 1
Таким образом, несмотря на кажущуюся хаотичность в процессе образования интернета, есть весьма жесткие статистические ограничения, которым он годами подчиняется. Почему это так? Что стоит за всеми свойствами интернета? Каковы законы, управляющие формированием сети?

Пейджем (Larry Page) на седьмой международной конференции World Wide Web (WWW7)

в апреле 1998 года.
Это алгоритм ранжирования с использованием гиперссылок в Интернете. На основе алгоритма, они построили поисковую систему Google
PageRank — это числовая величина, характеризующая «важность» веб-страницы. Чем больше ссылок на страницу, тем она становится «важнее». Таким образом, PageRank — это метод вычисления веса страницы путём подсчёта важности ссылок на неё.

– матчи. Вес ребра зависит от результата матча
Определение наиболее успешных

команд с помощью PageRank

число l
Вершины – все возможные слова длины l-1
Ребро из

вершины x в вершину y строится тогда, когда существует l-буквенное слово, для которого x является префиксом, y – суффиксом
Все графы де Брейна имеют эйлеров цикл

связанных дуг и узлов, местоположение и свойства которых с заданной

точностью и полнотой передают маршруты и организацию движения наземного транспорта.
http://www.gisinfo.ru/products/editroad.htm

вперед http://imat2010.yandex.ru/

Данные
Граф дорог. Перекрестки Москвы соответствуют вершинам
графа, а отрезки улиц

— дугам
Данные о пробках (загруженности дорог) Наблюдения
охватывают 31 день. Для первых 30 дней в файле
содержится информация о скорости движения потока
автотранспорта с 16:00 до 22:00; для последнего дня — с
16:00 до 18:00.

методов решения задач классификации и прогнозирования.
Иногда этот метод Data Mining также

называют деревьями решающих правил, деревьями классификации и регрессии.
Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например проверка качества сварки) и т.д.
Медицина. Диагностика различных заболеваний.
Молекулярная биология. Анализ строения аминокислот.

усердно", "Найдешь нефть!".

Выделение сообществ (кластеров) разных объектов: пользователей, сайтов, продуктовых

страниц интернет-магазинов:
Выделение сегментов пользователей для проведения рекламных кампаний.
Использование кластеров в качестве предикторов (прогностический параметр, средство прогнозирования) в персональных рекомендациях
Снижение размерности в любой задаче машинного обучения.
Сличение товарных URL между различными интернет-магазинами с целью выявления среди них групп, соответствующих одному и тому же товару.
Компактная визуализация — человеку будет проще воспринимать структуру данных.

– домены
Рёбра — аффинити между доменами.
Аффинити между доменами  — это

выборочная оценка того, насколько события «посещение юзером  домена » и «посещение юзером  домена » близки к независимости. 

цветом выделены кластеры)
https://habrahabr.ru/company/dca/blog/265077/