Теория графов (тема 10)

1.

Теория графов
Макарчук Роман
1

2.

Основы алгоритмизации и
программирования на JavaScript
Тема 1. Основы языка JavaScript
Тема 2. Типы данных и операции над ними
Тема 3. Этапы решения задачи на ЭВМ. Алгоритмы
Тема 4. Разветвленные алгоритмы. Условные операторы
Тема 5. Циклические алгоритмы. Операторы циклов
Тема 6. Списки. Массивы
Тема 7. Инструменты программирования
Тема 8. Демодень - Демонстрация разработанных программ
Тема 9. Функции и процедуры
Тема 10. Теория графов
Тема 11. Реализация принципов объектно-ориентированного программирования
Тема 12. Классификация языков
2

3.

Основы алгоритмизации и
программирования на JavaScript
Тема 10. Теория графов
10.1. Основные понятия теории графов
10.2. Деревья
10.3. Способы представления графов
10.4. Классические задачи теории графов
10.5. Двоичная куча
10.6. Сортировка кучей (пирамидальная сортировка)
3

4.

Основные
понятия
теории
графов
Основные
понятия
теории
графов
Использование
• географические карты и маршруты;
• расписание;
• гипертекст;
• компьютерные сети;
• социальные сети;
• рекомендательные системы;
• …

5.

Основные понятия теории графов
Граф (англ. graph) –
совокупность вершин (англ. vertex), или узлов (англ. node), и соединяющих
их ребер (англ. edge).
вершина
(узел)
2
4
6
1
3
ребро (дуга)
5

6.

Основные понятия теории графов
Ориентированный граф (направленный граф, орграф, англ. oriented graph, directed
graph, digraph) –
граф, в котором все ребра имеют направления.
Дуга –
направленное ребро.
2
4
6
1
3
5

7.

Основные
понятия
теории
графов
Основные
понятия
теории
графов
Взвешенный граф –
граф, в котором каждое ребро имеет вес.
5
1
12
2
4
2
6
4
9
3
7
5

8.

Основные
понятия
теории
графов
Основные
понятия
теории
графов
Инцидентность –
понятие, используемое только в отношении ребра или дуги и вершины. Если