Похожие презентации:
Теория графов (тема 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.
Основныепонятия
теории
графов
Основные
понятия
теории
графов
Инцидентность –
понятие, используемое только в отношении ребра или дуги и вершины. Если