Основные понятия Теории графов

Графы

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

Определение   Граф G — это совокупность двух конечных множеств: множества точек, которые называются вершинами, и множества пар вершин, которые называются ребрами.

Ребра могут быть:  смежными - пара неориентированных рёбер, имеющих общую вершину. кратными -вершины соединяются более, чем одним ребром. Если же концы одного ребра совпадают, то такое ребро называется петлей.

Степенью вершины  называют количество инцидентных ей ребер (т.е. ребер, входящих в вершину). При этом петли считают дважды.

таких Теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Одной из задач- головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).

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

Для решения этой задачи  Эйлер вводит понятие  «графа» как множества  непересекающихся рёбер ,  соединяющих пары вершин.  Вот так выглядит этот граф,  если наложить вершины и  связи на карту  города  Вывод: В графе, имеющим более  двух вершин с нечетной  степенью, такого обхода не  существует

П р а в и л о Э й л е р П р а в и л о Э й л е р а:а: 1.В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа. 2.В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой. 3.В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует

С графами встречаются: С графами встречаются:

Задача:

Виды графов Ориентированный Неориентированный Взвешенный 2 3 1 5 ОриентированныйНеориентированныйВзвешенный

Неориентированный граф – в котором связи не направлены. Маша Петя Таня Саша Катя Аня Коля Миша Граф дружбы МашаПетяМишаКоляАняКатяТаняСашаГраф дружбы

Ориентированный граф – в котором связи направлены. Рождени е Юность Зрелость Старость Граф жизни Смерть РождениеЮностьЗрелостьСтаростьСмертьГраф жизни

Взвешенный граф в котором рёбра содержат дополнительную информацию. 10 5 1 +9 -5 -7 -1 8 9 +2 -1 7 6 +9 0 -6 189105760

Взвешенный граф союз СССР война США война ЯПОНИЯ война война ГЕРМАНИЯ союз СССРГЕРМАНИЯСШАЯПОНИЯ

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

Иерархический граф Иерархия – это расположение частей или элементов целого в порядке от высшего к низшему. Это – граф отношения подчиненности в школе: Директор Заместитель директора Учителя Ученики Иерархия – это расположение частей или элементов целого в порядке от высшего к низшему. Это – граф отношения подчиненности в школе:ДиректорЗаместитель директораУченикиУчителя

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

Итак, виды графов: Ориентированный Неориентированный Взвешенный Иерархический Дерево Мультиграф Псевдограф

Задача: На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Задача: У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Задача. В бутылке, стакане, кувшине и банке  находятся молоко, лимонад, квас и вода.  Известно, что вода и молоко не в бутылке,  сосуд с лимонадом стоит между кувшином и  сосудом с квасом, в банке не лимонад и не  вода. Стакан стоит около банки и сосуда с  молоком. Куда налита каждая жидкость? Начертим таблицу: Молоко Лимонад Квас Вода Бутылка Стакан Кувшин Банка

Бутылка Стакан Кувшин Банка Молоко Лимонад Квас - - - + - - + - + - - - Вода - + - - 1. Вода и молоко не в бутылке. 2. В банке не лимонад и не вода. 3. Молоко  Банка  Стакан. (?) 4. В кувшине молоко, поэтому везде, кроме молока, ставим -. 5. Тогда понятно, что квас налит в банку. 6. Вода в стакане. 7. Лимонад в бутылке.

Решение с помощью графа: Красными линиями соединим вершины, которые не могут быть связаны друг с другом. Синими линиями соединим вершины, которыми возможно могут быть связаны друг с другом. Зелеными линиями соединим вершины, которые связаны друг с другом. БУТЫЛКА СТАКАН БАНКА КУВШИН МОЛОКО ЛИМОНА Д КВАС ВОДА Ответ: бутылка-лимонад, стакан-вода, банка-квас, кувшин-молоко. БУТЫЛКАСТАКАНБАНКАКУВШИНМОЛОКОЛИМОНАДКВАСВОДА

Графы придают условиям задачи наглядность, упрощают решение, выявляют сходство задач. Сейчас в любой отрасли науки и техники встречаешься с графами: Электротехники при построении электрических схем Тур-компании при систематизации маршрутов

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

Составить граф 1) (1, 2), (2, 3), (3, 1), (3, 5),(5, 4), (4, 2) (1, 3) , (2, 1), (3, 2), (3, 4), (4, 5), 3). (5, 3).

Задача: (дополнительно) В группе учатся 40 студентов. Из них по русскому языку имеют «пятерки» 19 человек, по математике – 17 человек и по информатике – 22 человека. Только по одному предмету имеют «пятерки»: по русскому языку – 4 человека, по математике – 4 человека, по информатике – 11 человек. Семь студентов имеют «пятерки» и по математике и по информатике, а 5 студентов – «пятерки» по всем предметам. Сколько человек учится без «пятерок»? Сколько человек имеют «пятерки» по двум из трех предметов?