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

Июль 22, 2022

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

Содержание

2. «Отец» теории графов Леонард Эйлер Задача о семи мостах Кенигсберга Письмо итальянскому математику и инженеру Маринони
3. Мосты Кенигсберга
4. Если дана геометрическая фигура, как начертить ее на бумаге одним росчерком пера, не проводя дважды ни
5. Прикладные задачи 1847 год Физик Густав Роберт Кирхгоф Теория графов для исследования электрических цепей Множество фундаментальных
6. Прикладные задачи 1857 год Математик Артур Кэли Задачи органической химии
7. Перечислить число предельных углеводородов с данным числом n атомов углерода На языке графов: найти число всех
8. Головоломки 1859 год Сэр Уи́льям Ро́уэн Га́мильтон Головоломка «Вокруг света»
9. Головоломка «Вокруг света» Додекаэдр, каждому из 20 вершин приписано название города Обойти «вокруг света» по ребрам
11. Задача коммивояжера (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен посетить N городов,
12. Задача о домиках и колодцах Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся
13. Полный двудольный граф К3,3 Доказано, что данный граф непланарен, то есть задача о домиках и колодцах
14. Задача о раскраске карт или гипотеза о четырех красках 1850-1852 г.г. (приблизительно) Ф.Гатри постановка задачи: «сколько
15. Задача о раскраске карт или гипотеза о четырех красках 1879 г. британский математик Альфред Брей Кемпе
16. 1975 г. известный популяризатор науки и многолетний ведущий раздела «Математические игры» журнала «Scientific American» Мартин Гарднер
17. 1976 г. два математика из Иллинойского университета, Вольфганг Хакен и Кеннет Аппель, предложили новый метод, перевернувший
18. Примеры Вершины – города, ребра - дороги между ними Вершины – города, ребра – наличие авиарейса
19. Теория графов в игре престолов https://habrahabr.ru/post/302936/ Граф социальной активности Вершинам соответствуют персонажи; размер вершины зависит от
21. Общие сведения о графе Граф неориентированный. Вершин (персонажей): 1105 Рёбер (диалогов): 3505 5 книг, почти 2
22. Алгоритмы на графе Подсчет степеней вершин – самые многосвязные персонажи Диаметр графа (расстояние между наиболее удаленными
23. Распределение длин путей
24. Остовное дерево (алгоритм Краскала) Главные герои и их связи
25. Математическая модель интернета – веб-граф (А.Райгородский) http://elementy.ru/nauchno-populyarnaya_biblioteka/431792/Matematicheskie_modeli_interneta Вершинами этого графа будут сайты, и между двумя вершинами
26. Свойства веб-графа Диаметр веб-графа равен 6 (закон шести рукопожатий) Веб-граф является достаточно разреженным: если вершин у
27. Алгоритм PageRank PageRank был представлен и опубликован Сергеем Брином (Sergey Brin) и Ларри Пейджем (Larry Page)
28. Алгоритм PageRank и футбольные команды https://geektimes.ru/post/247244/ Вершины графа – команды, ребра – матчи. Вес ребра зависит
29. Теория графов и реконструкция генома http://kvant.mccme.ru/pdf/2014/2014-03.pdf Граф де Брейна: Алфавит из n букв, число l Вершины
31. Гамильтонов цикл в графе де Брейна
32. Граф дорог – это цифровая векторная карта, состоящая из топологически связанных дуг и узлов, местоположение и
33. Яндекс – школа данных Задача о предсказании пробок на небольшой промежуток времени вперед http://imat2010.yandex.ru/ Данные Граф
34. Метод деревьев решений (decision trees) является одним из наиболее популярных методов решения задач классификации и прогнозирования.
35. Выдача кредита
36. Формула Ж. Поля Гетти "Как стать богатым": "Вставай рано", "Работай усердно", "Найдешь нефть!".
39. Анализ больших данных. Поиск сообществ в графах. Задачи кластеризации Выделение сообществ (кластеров) разных объектов: пользователей, сайтов,
40. ПОИСК СООБЩЕСТВ В НЕОРИЕНТИРОВАННЫХ ГРАФАХ (ГРАФ ДОМЕНОВ РУНЕТА - 1285) https://habrahabr.ru/company/dca/blog/265077/ Вершины – домены Рёбра —
42. Скачать презентацию

Слайд 2

«Отец» теории графов Леонард Эйлер
Задача о семи мостах Кенигсберга
Письмо итальянскому математику

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

Слайд 3

Мосты Кенигсберга

Слайд 4

Если дана геометрическая фигура, как начертить ее на бумаге одним росчерком

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

Слайд 5

Прикладные задачи
1847 год
Физик Густав Роберт Кирхгоф
Теория графов для исследования электрических цепей
Множество

фундаментальных циклов в графе

Слайд 6

Прикладные задачи
1857 год
Математик Артур Кэли
Задачи органической химии

Слайд 7

Перечислить число предельных углеводородов с данным числом n атомов углерода
На языке

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

Слайд 8

Головоломки
1859 год
Сэр Уи́льям Ро́уэн Га́мильтон
Головоломка «Вокруг света»

Слайд 9

Головоломка «Вокруг света»
Додекаэдр, каждому из 20 вершин приписано название города
Обойти «вокруг

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

Слайд 10

Слайд 11

Задача коммивояжера (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен

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

Слайд 12

Задача о домиках и колодцах
Три поссорившихся соседа имеют три общих

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

Слайд 13

Полный двудольный граф К3,3
Доказано, что данный граф непланарен, то есть задача

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

Слайд 14

Задача о раскраске карт или гипотеза о четырех красках
1850-1852 г.г. (приблизительно)

Ф.Гатри постановка задачи: «сколько потребуется красок для раскраски любой плоской карты таким образом, чтобы никакие две смежные области не были окрашены в один и тот же цвет»
Гипотеза: достаточно четырех красок

Слайд 15

Задача о раскраске карт или гипотеза о четырех красках
1879 г. британский

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

Слайд 16

1975 г. известный популяризатор науки и многолетний ведущий раздела «Математические игры» журнала

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

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

Слайд 17

1976 г. два математика из Иллинойского университета, Вольфганг Хакен и Кеннет Аппель,

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

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

Слайд 18

Примеры
Вершины – города, ребра - дороги между ними
Вершины – города, ребра

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

Слайд 19

Теория графов в игре престолов
https://habrahabr.ru/post/302936/
Граф социальной активности
Вершинам соответствуют персонажи; размер вершины

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

Слайд 20

Слайд 21

Общие сведения о графе
Граф неориентированный. Вершин (персонажей): 1105 Рёбер (диалогов): 3505
5 книг, почти 2

миллиона слов.
Для сбора данных было привлечено машинное обучение (точность определения принадлежности разговора составляет около 75%).

Слайд 22

Алгоритмы на графе
Подсчет степеней вершин – самые многосвязные персонажи
Диаметр графа (расстояние

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

Слайд 23

Распределение длин путей

Слайд 24

Остовное дерево
(алгоритм Краскала)
Главные герои и их связи

Слайд 25

Математическая модель интернета – веб-граф (А.Райгородский)
http://elementy.ru/nauchno-populyarnaya_biblioteka/431792/Matematicheskie_modeli_interneta
Вершинами этого графа будут

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

Слайд 26

Свойства веб-графа
Диаметр веб-графа равен 6 (закон шести рукопожатий)
Веб-граф является достаточно разреженным:

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

Слайд 27

Алгоритм PageRank
PageRank был представлен и опубликован Сергеем Брином (Sergey Brin) и Ларри Пейджем

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

Слайд 28

Алгоритм PageRank и футбольные команды https://geektimes.ru/post/247244/
Вершины графа – команды, ребра –

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

Слайд 29

Теория графов и реконструкция генома
http://kvant.mccme.ru/pdf/2014/2014-03.pdf
Граф де Брейна:
Алфавит из n букв, число

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

Слайд 30

Слайд 31

Гамильтонов цикл в графе де Брейна

Слайд 32

Граф дорог – это цифровая векторная карта, состоящая из топологически связанных

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

Слайд 33

Яндекс – школа данных
Задача о предсказании пробок на небольшой промежуток
времени вперед

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

Слайд 34

Метод деревьев решений (decision trees) является одним из наиболее популярных методов

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

Слайд 35

Выдача кредита

Слайд 36

Формула Ж. Поля Гетти "Как стать богатым": "Вставай рано", "Работай усердно",

"Найдешь нефть!".

Слайд 37

Слайд 38

Слайд 39

Анализ больших данных. Поиск сообществ в графах. Задачи кластеризации
Выделение сообществ

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

Слайд 40

ПОИСК СООБЩЕСТВ В НЕОРИЕНТИРОВАННЫХ ГРАФАХ (ГРАФ ДОМЕНОВ РУНЕТА - 1285)
https://habrahabr.ru/company/dca/blog/265077/
Вершины –

домены
Рёбра — аффинити между доменами.
Аффинити между доменами — это выборочная оценка того, насколько события «посещение юзером домена » и «посещение юзером домена » близки к независимости.

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

Содержание

«Отец» теории графов Леонард ЭйлерЗадача о семи мостах КенигсбергаПисьмо итальянскому математику

Мосты Кенигсберга

Если дана геометрическая фигура, как начертить ее на бумаге одним росчерком

Прикладные задачи1847 годФизик Густав Роберт КирхгофТеория графов для исследования электрических цепейМножество

Прикладные задачи1857 годМатематик Артур КэлиЗадачи органической химии

Перечислить число предельных углеводородов с данным числом n атомов углеродаНа языке

Головоломки1859 годСэр Уи́льям Ро́уэн Га́мильтонГоловоломка «Вокруг света»

Головоломка «Вокруг света»Додекаэдр, каждому из 20 вершин приписано название городаОбойти «вокруг

Задача коммивояжера (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен

Задача о домиках и колодцах Три поссорившихся соседа имеют три общих

Полный двудольный граф К3,3Доказано, что данный граф непланарен, то есть задача

Задача о раскраске карт или гипотеза о четырех красках1850-1852 г.г. (приблизительно)

Задача о раскраске карт или гипотеза о четырех красках1879 г. британский

1975 г. известный популяризатор науки и многолетний ведущий раздела «Математические игры» журнала

1976 г. два математика из Иллинойского университета, Вольфганг Хакен и Кеннет Аппель,

ПримерыВершины – города, ребра - дороги между нимиВершины – города, ребра

Теория графов в игре престоловhttps://habrahabr.ru/post/302936/Граф социальной активностиВершинам соответствуют персонажи; размер вершины

Общие сведения о графеГраф неориентированный. Вершин (персонажей): 1105 Рёбер (диалогов): 35055 книг, почти 2

Алгоритмы на графеПодсчет степеней вершин – самые многосвязные персонажиДиаметр графа (расстояние