Элементы теории графов. Задачи, сводящиеся к графам

Сентябрь 12, 2022

Главная
Математика
Элементы теории графов. Задачи, сводящиеся к графам

Содержание

2. СОДЕРЖАНИЕ: Теория графов. История возникновения. Что же такое граф? Связность. Теоремы о связности. Задача о кёнигсбергских
3. ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория
4. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих
5. ЧТО ЖЕ ТАКОЕ ГРАФ? Граф G = есть совокупность множества вершин V и множества рёбер (дуг)
6. ориентированный неориентированный
7. СВЯЗНОСТЬ Пусть граф G — неориентированный. Две вершины a и b называются связанными, если существует путь
8. ТЕОРЕМЫ О СВЯЗНОСТИ. Если в конечном неориентированном простом графе G ровно две вершины a и b
9. ЗАДАЧА О КЁНИГСБЕРГСКИХ МОСТАХ. Как пройти по всем мостам(через реку Преголя), не проходя ни по одному
10. ВЫВОДЫ ЭЙЛЕРА: Число нечётных вершин графа должно быть чётно. Не может существовать граф, который имел бы
11. ПРИМЕРЫ ЗАДАЧ: Задача 1. Лист бумаги Плюшкин (Н.В.Гоголь "Мертвые души") разрезает на три части. Некоторые из
12. Задача 2. Утверждают, что в одной компании из пяти человек каждый знаком с двумя другими. Возможна
13. . ДЕРЕВЬЯ Связные графы, в которых существует одна и только одна цепь, соединяющая каждую пару вершин,
14. Схема проведения игр изображается графом Вершины нижнего "яруса" дерева интерпретируем как команды, участвующие в розыгрыше кубка,
15. Примечание. Список используемой литературы. http://textarchive.ru/c-1728339-pall.html https://www.hse.ru/data/2010/10/14/1223122510/DA_Teor_Graph.pdf http://www.math.mrsu.ru/text/courses/method/osn_pon_teor_graph.htm http://ougeorg.kormil.obr55.ru/matem2.doc http://dfgm.math.msu.su/files/0ngit/shafarevich/lecture1.pdf
17. Скачать презентацию

Слайд 2

СОДЕРЖАНИЕ:
Теория графов.
История возникновения.
Что же такое граф?
Связность.
Теоремы о связности.
Задача о кёнигсбергских мостах.
Выводы

Эйлера.
Примеры задач.
«Деревья» .
Приложение.

Слайд 3

ТЕОРИЯ ГРАФОВ
- это область дискретной математики, особенностью которой является геометрический

подход к изучению объектов. Теория графов пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения.

Слайд 4

ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ
Родоначальником теории графов считается Леонард Эйлер. В 1736

году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах , ставшей впоследствии одной из классических задач теории графов.

Слайд 5

ЧТО ЖЕ ТАКОЕ ГРАФ?
Граф G =< V, E > есть совокупность

множества вершин V и множества рёбер (дуг) , причем E ⊆ V × V есть множество упорядоченных пар < x, y > для ориентированного графа и E ⊆ {{x, y} : (x, y ∈ V)&(x 6= y)} для неориентированного графа (при этом для неориентированного графа считаем, что ребра {a, b} и {b, a} совпадают {a, b} = {b, a}). Граф неориентированный, если все его ребра не ориентированы, и граф ориентированный, если все его ребра ориентированы.

Слайд 6

ориентированный
неориентированный

Слайд 7

СВЯЗНОСТЬ
Пусть граф G — неориентированный. Две вершины a и b называются

связанными, если существует путь S с начальной вершиной a и конечной вершиной b, S =< a, a1, ..., an, b >. Если S проходит через какую-нибудь вершину ai более одного раза, то можно, очевидно, удалить его циклический участок и при этом остающиеся ребра будут составлять путь S 0 из a в b. Отсюда следует, что связанные путем вершины связаны и простым путем. Граф называется связным, если любая его пара вершин связана.

Слайд 8

ТЕОРЕМЫ О СВЯЗНОСТИ.
Если в конечном неориентированном простом графе G ровно две

вершины a и b имеют нечетную локальную степень, то они связаны.
Если неориентированный простой граф G имеет n вершин и k связных компонент, то максимальное число ребер в G равно
N(n, k) = 0.5(n − k)(n − k + 1).
Простой неориентированный граф с n вершинами и с числом ребер, большим, чем N(n, 2) = 0.5(n − 1)(n − 2) связан.

Слайд 9

ЗАДАЧА О КЁНИГСБЕРГСКИХ МОСТАХ.
Как пройти по всем мостам(через реку Преголя), не

проходя ни по одному из них дважды?

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

Слайд 10

ВЫВОДЫ ЭЙЛЕРА:
Число нечётных вершин графа должно быть чётно. Не может существовать

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

Слайд 11

ПРИМЕРЫ ЗАДАЧ:
Задача 1. Лист бумаги Плюшкин (Н.В.Гоголь "Мертвые души") разрезает на три

части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листков он вновь разрезает на три более мелкие части и так далее. Сколько Плюшкин получает листиков бумаги, если разрезает листов?
Решение. Будем считать листы бумаги вершинами графа. При разрезании одного листка на три части число листков увеличивается на два (появляются три новых вместо одного). Если же было разрезано листов, то образовалосьлистов.

Слайд 12

Задача 2. Утверждают, что в одной компании из пяти человек каждый знаком

с двумя другими. Возможна ли такая компания?

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

Слайд 13

.
ДЕРЕВЬЯ
Связные графы, в которых существует одна и только одна цепь,

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

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

Слайд 14

Схема проведения игр изображается графом
Вершины нижнего "яруса" дерева интерпретируем как команды,

участвующие в розыгрыше кубка, вершины второго снизу яруса — как команды-победительницы в финала, вершины третьего яруса — как команды-победительницы в финала и т.д.
Какую информацию можно получить с помощью этого дерева?
Непосредственно с него считываются:

1)Число всех участников розыгрыша кубка (число вершин нижнего "яруса")

2)Число этапов проведения розыгрыша (число "ярусов" из вершин в дереве, не считая нижнего).

3)Число команд, участвующих в финала, в финала, в финала (число вершин, соответственно, в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе).

Слайд 15

Примечание. Список используемой литературы.
http://textarchive.ru/c-1728339-pall.html
https://www.hse.ru/data/2010/10/14/1223122510/DA_Teor_Graph.pdf
http://www.math.mrsu.ru/text/courses/method/osn_pon_teor_graph.htm
http://ougeorg.kormil.obr55.ru/matem2.doc
http://dfgm.math.msu.su/files/0ngit/shafarevich/lecture1.pdf

Элементы теории графов. Задачи, сводящиеся к графам

Содержание

СОДЕРЖАНИЕ:Теория графов.История возникновения.Что же такое граф?Связность.Теоремы о связности.Задача о кёнигсбергских мостах.Выводы

ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический

ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ Родоначальником теории графов считается Леонард Эйлер. В 1736

ЧТО ЖЕ ТАКОЕ ГРАФ?Граф G =< V, E > есть совокупность

ориентированныйнеориентированный

СВЯЗНОСТЬПусть граф G — неориентированный. Две вершины a и b называются

ТЕОРЕМЫ О СВЯЗНОСТИ.Если в конечном неориентированном простом графе G ровно две

ЗАДАЧА О КЁНИГСБЕРГСКИХ МОСТАХ. Как пройти по всем мостам(через реку Преголя), не

ВЫВОДЫ ЭЙЛЕРА:Число нечётных вершин графа должно быть чётно. Не может существовать

ПРИМЕРЫ ЗАДАЧ:Задача 1. Лист бумаги Плюшкин (Н.В.Гоголь "Мертвые души") разрезает на три