Графы. Решение задач на применение графов.

Графы

.

• Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг.

Денни Кенинг

• Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана еще в 1736 г.

Леонард Эйлер

С помощью графов изображаются схемы :

-различных дорог,

-линии воздушных сообщений,

-газопроводов,

-теплотрасс,

-электросетей,

-микросхемы,

-химические структурные формулы

-и др.

Задача о Кёнигсбергских мостах

• Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку

• Эта задача была решена Эйлером в 1736 году.

Графом  называется структура простейшей связной системы, состоящей из множества вершин и множества ребер.

-элементы графа называют вершинами .

-связь между двумя различными вершинами графа называют   ребром .

• Две вершины называются смежными , если они связаны ребром.

• Два ребра называются смежными , если они имеют общую вершину.
• Ребро, связанное с вершиной, называется  инцидентным  данной вершине.

Степень вершины графа

• Число ребер инцидентных данной вершине называется её  степенью .

• Степень вершины  vi  обычно обозначают как  degvi

Граф G4 содержит четыре вершины:

V= (A,В, С, D)

и шесть ребер Х= {р, q, r, s, t, и}.

Записать, чему равна

степень вершин:

deg (A) =

deg (В) =

deg (С) =

deg (D) =

Простой граф

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

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

Псевдограф

• Граф, который имеет хотя бы одну петлю называется псевдографом

Мультиграф

• Граф, у которого между двумя вершинами существует более одной связи называется мультиграфом

Назовите виды графов

Орграф

• Граф с направленными связями называют ориентированным графом орграфом или направленным.

Взвешенный граф

• Граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра)

Путь

В орграфе маршрут является ориентированным и называется путем .

Ориентированный граф в электрической схеме

• Решение задачи о Кёнигсбергских мостах

Эйлеров граф

• Эйлеров путь  в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

• Эйлеров цикл  — это эйлеров путь, являющийся циклом.

Условия существования Эйлерова графа

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

• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Эйлеров путь в графе

Эйлеров граф

ГРАФЫ. РЕШЕНИЕ ЗАДАЧ.

Задание 1. Определите степень вершин графа и сделайте вывод о существовании Эйлерова пути в графе

Матрица смежности

• Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.

• Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе – 0.

Матрица смежности

Задание 2. Постройте произвольный граф из 6 вершин и составьте для него матрицу смежности

• Образец

Матрица ориентированного графа

• Если граф ориентированный то при составлении матрицы смежности учитывается направление ребра ( 0 или 1)

Взвешенные графы

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

Задание 3

• Проверьте выполнение условия Эйлерова графа
• Сделайте граф взвешенным
• Составьте для данного графа матрицу смежности

Задание 4

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

РЕШЕНИЕ

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

• Ответ : Клен, яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задание 5

• Пятеро учёных обменялись рукопожатиями. Сколько всего рукопожатий было сделано?

• Пятеро учёных обменялись рукопожатиями. Сколько всего рукопожатий было сделано?