Применение графов

Что такое граф
В математике определение графа дается так:
Графом называется конечное множество точек, некоторые из которых соединены линиями.
Точки называются вершинами графа, а соединяющие линии – рёбрами.
Рёбра графа
Вершина графа
Дальше

История возникновения графов
Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.
содержание

Задача о Кенигсбергских мостах
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
Дальше

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

дальше
Я здесь уже был!

Задача о Кенигсбергских мостах
Пройти по Кенигсбергским мостам, соблюдая заданные условия, нельзя. Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа.
дальше

Задача о Кенигсбергских мостах
Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то такой граф начертить «одним росчерком» невозможно.
содержание

Свойства графа
Ориентированный граф Неориентированный граф

Маршрут в графе это путь, ориентацией дуг которого можно пренебречь.
Цепь - маршрут, в котором все ребра попарно различны.
Цикл - замкнутый маршрут, являющийся цепью.
Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.
Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины.
A, C, A, D – маршрут, но не цепь;
A, C, E, B, C, D – цепь, но не простая цепь;
A, D, C, B, E, - простая цепь;
A, C, E, B, C, D, A – цикл, но не простой цикл;
A, C, D – простой цикл;

Одним росчерком
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым.
Решая задачу О кенигсбергских мостах, Эйлер сформулировал свойства графа:
Невозможно начертить граф с нечетным числом нечетных вершин.
дальше

Одним росчерком
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
дальше

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

Одним росчерком
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
?
содержание

Применение графов
Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
дальше

Первый многосвязный садовый лабиринт был сооружён в 1820-е годы в Чевнинге в Великобритании.

ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО ОДИН РАЗ.
ГРАФ, СОДЕРЖАЩИЙ ГАМИЛЬТОНОВ ЦИКЛ, НАЗЫВАЕТСЯ ГАМИЛЬТОНОВЫМ.
A
B
C
D
E
(C, D, A, B, E) – гамильтонов путь

В 1857 году ирландский математик Гамильтон предложил игру, названную «Путешествием по додекаэдру». Игра сводилась к обходу по ребрам всех вершин правильного додекаэдра, при условии, что ни в одну из вершин нельзя заходить более одного раза.

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

ТЕОРЕМА
В ГРАФЕ СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ РЕБЕР ГРАФА:
ТЕОРЕМА
ЧИСЛО НЕЧЕТНЫХ ВЕРШИН ЛЮБОГО ГРАФА – ЧЕТНО.
СЛЕДСТВИЕ
ЧИСЛО ВЕРШИН МНОГОГРАННИКА, В КОТОРЫХ СХОДИТСЯ НЕЧЁТНОЕ ЧИСЛО РЁБЕР, ЧЁТНО.
Степень А +степень В + степень С +…= 2*число рёбер
НЕЧЁТНОЕ ЧИСЛО ЗНАКОМЫХ В ЛЮБОЙ КОМПАНИИ ВСЕГДА ЧЁТНО.

ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ.
ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ ГРАФ С ТЕМИ ЖЕ ВЕРШИНАМИ И ИМЕЮЩИЙ ТЕ И ТОЛЬКО ТЕ РЕБРА, КОТОРЫЕ НЕОБХОДИМОДОБАВИТЬ К ИСХОДНОМУ ГРАФУ, ЧТОБЫ ОН СТАЛ ПОЛНЫМ.
ДОПОЛНЕНИЕ ГРАФА ДО ГРАФА

ЦИКЛ – ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И КОНЕЦ.

G, H, E, B, A - ВИСЯЧИЕ ВЕРШИНЫ
Деревом называется связный граф, не имеющий циклов

Задание неориентированного графа с помощью матриц
Матрица инцидентности. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующего рёбрам. Если граф неориентированный, то ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
Матрица смежности. Это матрица n×n где n - число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у, и bij = 0 в противном случае.
Матрицы инцидентности и смежности для следующего графа :

Задание ориентированного графа с помощью матриц
Каждый элемент матрицы смежности определяется следующим образом:
aij = 1, если существует дуга (хi, хj),
aij = 0, если нет дуги (хi, хj).
Каждый элемент матрицы инциндентности определяется следующим образом:
bij = 1, если хi является начальной вершиной дуги aj,
bij = –1, если хi является конечной вершиной дуги aj,
bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.
Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциндентности

Изоморфные графы

Изоморфизм графов
Два графа G=(V1, E1), H=(V2, E2) называются изоморфными, если существует соответствие между вершинами графа G и вершинами графа H, сохраняющее отношение смежности.
Изоморфные графы отличаются только метками вершин.
Любой неориентированный граф превращается в орграф заменой каждого ребра двумя противоположно направленными ребрами. Два полученные таким образом орграфа, очевидно, изоморфны тогда и только тогда, если изоморфны исходные графы.

Применение графов
Использует графы и дворянство.
На рисунке приведена часть генеалогического дерева знаменитого дворянского рода Л. Н. Толстого. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.
дальше

Задача №1.
Перечислить все возможные варианты обедов из трех блюд (одного первого, одного второго и одного третьего блюда), если в меню столовой имеются два первых блюда: щи (щ) и борщ (б); три вторых блюда: рыба (р), гуляш (г) и плов (n); два третьих: компот (к) и чай (ч).
Решение.

Применение графов
Задача 1:
Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
дальше

Применение графов
Решение:
А
Г
В
Б
Д
1
2
3
4
5
6
7
8
9
10
дальше

Задача 2. По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали:
1) 3 человека; 2) 4 человека; 3) 5 человек?
1) Во встрече участвовали 3 человека:
2) Во встрече участвовали 4 человека:
3) Во встрече участвовали 5 человек.

Логические задачи

Задача «Подружки»
У трёх подружек - Ксюши, Насти и Оли - новогодние карнавальные костюмы белого, фиолетового и синего цветов, и шапочки тех же цветов. У Насти цвет костюма и шапочки совпали, у Ксюши ни костюм, ни шапочка не были фиолетового цвета, а Оля была в белой шапочке, но цвет костюма у неё не был белым.
Как были одеты девочки?

1. Костюм и шапочка Насти одного цвета.
2. Костюм и шапочка Ксюши не фиолетового цвета.
3. Оля в белой шапочке.
4. Костюм у Оли не белый.
подружки
костюмы
шапочки
Ксюша Оля Настя
Бел.
Фиол.
Син.
Бел.
Фиол.
Син.
Ксюша не в фиолетовой шапочке и не в белой, значит, в синей, а у Насти – фиолетовая шапочка.
У Насти цвета шапочки и костюма совпадают по условию, а у Оли – не совпадают.
Вывод: Настя в фиолетовом костюме и шапочке,
Ксюша в белом костюме и синей шапочке,
Оля в синем костюме и белой шапочке.

Вывод:
Настя в фиолетовом костюме и шапочке,
Ксюша в белом костюме и синей шапочке,
Оля в синем костюме и белой шапочке.

Задача «Учительницы»
Три учительницы - Ирина Васильевна, Дарья Михайловна и Софья Петровна - преподают химию, биологию и физику в школах Ярославля, Владимира и Краснодара. Известно, что
И.В. работает не в Ярославле, а Д.М. - не во Владимире;
та, которая живет в Ярославле, преподает не физику;
работающая во Владимире – учитель химии;
Д.М. преподает не биологию.
Кто в каком городе живет и какой предмет преподает?

И.В. Д.М. С.П.
Яр.
Вл.
Кр.
хим.
биол.
физ.
1. И.В. работает не в Ярославле, а Д.М. - не во Владимире;
та, которая живет в Ярославле, преподает не физику;
3. работающая во Владимире – учитель химии;
4. Д.М. преподает не биологию.
Вывод: Д.М. не биолог и не химик, следовательно, преподает физику.
Вывод: в Ярославле живет учитель биологии (т.к. не физика и не химия), тогда физик - в Краснодаре.
Итак, Д.М. – физик из Краснодара, И.В. – живет во Владимире (т.к. не в Ярославле) и преподает химию, тогда С.П. – ярославна - биолог.

Итак:
Д.М. – физик из Краснодара,
И.В. – живет во Владимире (т.к. не в Ярославле) и преподает химию,
С.П. – из Ярославля - биолог.

В одном дворе живут четыре друга.
Вадим и шофер старше Сергея,
Николай и слесарь занимаются боксом,
Электрик-младший из друзей.
По вечерам Андрей и токарь играют в домино против Сергея и электрика.
Определите профессию каждого из друзей.
Условие задачи

Вадим
Коля
Сергей
Андрей
слесарь
токарь
электрик
шофер
Начинаем анализировать полученную схему.
От каждого верхнего кружка должно исходить 4 линии к кружкам нижнего ряда,одна из которых сплошная(прочная связь) ,три-пунктирные. (разрывная связь). И от кружков нижнего ряда-аналогично.
От Сергея отходит 3 разрывные связи, значит, четвертая- прочная связь
Ответ готов:
Вадим-токарь, Сергей-слесарь, Коля-электрик, Андрей-шофер

Известно, что в настоящий момент:
Ваня сыграл шесть партий;
Толя сыграл пять партий;
Леша и Дима сыграли по три партии;
Семен и Илья сыграли по две партии;
Женя сыграл одну партию.
Условие задачи
Требуется определить:
с кем сыграл Леша.
Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с каждым ровно один раз, участвуют семь школьников.

Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Изобразим участников турнира точками
Для каждой точки укажем ее имя
(по первой букве имени игрока)
и количество партий, сыгранные этим игроком

Начать построение ребер следует с вершины В, так как это единственная вершина,
которая соединяется со всеми другими вершинами графа
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Будем строить ребра графа с учетом степеней вершин

Для вершин В и Ж построены все возможные ребра
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Сделаем первые выводы:

Теперь однозначно определяются ребра вершины Т.
С учетом ребра ВТ надо построить четыре ребра
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Построим следующие ребра

Все возможные ребра теперь построены для вершин Ж, В, Т, а также для вершин С и И
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Пора делать новые выводы

ОТВЕТ: Леша играл с Толей, Ваней и Димой
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Требовалось определить: с кем сыграл Леша.
Граф к задаче построен