Графы. Применение графов к решению задач

1.

ГРАФЫ. ПРИМЕНЕНИЕ
ГРАФОВ К РЕШЕНИЮ
ЗАДАЧ
ВЫПОЛНИЛИ СТУДЕНТЫ
ГРУППЫ «ПС-18»:
НОГОВИЦИН АНДРЕЙ,
ЛОМАКИНА ЕЛЕНА

2.

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

3.

Граф называется ориентированным, если указано
направление дуг и неориентированным, если такое
направление не указано.
Две вершины называются смежными, если существует
соединяющая их дуга.
Примеры графов:

4.

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

5.

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

6.

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

7.

Связанный граф -это граф, у которого любые две вершины
связанны. Если граф несвязен, то в нем можно выделить так
называемые связанные компоненты (т.е. множества вершин,
соединенных ребрами исходного графа, каждое из которых является
связным графом).
Ребро связного графа G называется мостом, если после его
удаления граф станет несвязным и распадется на два связных
подграфа.
Точкой сочленения графа называется вершина, удаление которой
приводит к увеличению числа его компонент связности.
На рисунке 1 ребро k – мост, а на рисунке 2 вершина 1 – точка
сочленения.
Рис 1
Рис 2

8.

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

9.

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

10.

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

11.

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

12.

Задача 1.
Для неориентированного графа построить
матрицу смежности S и матрицу инцидентности T.

13.

Задача 2.
Составить список степеней вершин графа.