Количество рёбер, выходящих из вершины графа, называется степенью вершины.

Вершина графа, имеющая нечётную степень, называется нечётной, а чётную степень — чётной.

Изолированная вершина — вершина, степень которой равна 0.
Конечная вершина графа — вершина, степень которой равна 1.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлёй.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Граф называется неориентированным, если его вершины соединены ребрами.
Цепь — путь по вершинам и рёбрам, включающий любое ребро графа не более одного раза.
Цикл — цепь, начальная и конечная вершины которой совпадают.
Граф с циклом называют сетью.
Ориентированный граф — граф, рёбрам которого присвоено направление.

Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

История возникновения теории графов

Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.

Оригинальная статья Л.Эйлера

ТЕОРИЯ ГРАФОВ. ГРАФЫ, ДЕРЕВЬЯ И СЕТИ
Содержание:
1.Семь мостов города Кенигсберга
2.Головоломка Гамильтона
3.Алгоритм определения циклов
4.Алгоритмы обхода графа
5.Поиск в глубину
6.Поиск в ширину (Волновой алгоритм)
7.Алгоритм Дейкстры
8.Алгоритм Флойда
9.Алгоритм Прима
10.Алгоритм Крускала
leksiya2.pdf
Adobe Acrobat документ 501.2 KB

Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)).

Деревья и сети

Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему.
Системы, элементы которых находятся в отношениях подчинённости, называются иерархическими системами.

Дерево — граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

Корень — главная вершина дерева.
Предок — объект верхнего уровня.
Потомок — объект нижнего уровня.

Листья — вершины, не имеющие потомков.