Основные понятия теории графов

Август 6, 2022

Главная
Математика
Основные понятия теории графов

Содержание

2. Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения всех четырех частей суши в
3. Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами, и конечного множества элементов, называемых
4. Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek. Ребра с одинаковыми концевыми
5. Изолированная вершина не инцидентна ни одному ребру (v3). Две вершины смежны, если они являются концевыми вершинами
6. Подграф – любая часть графа, сама являющаяся графом. Основные понятия Подграф H графа G
7. Граф G=(V,E) называется простым, если он не содержит петель и параллельных ребер. Виды графов Граф G=(V,E)
8. Виды графов Ноль-граф - граф, множество ребер которого пусто. Граф G с кратными ребрами называется мультиграф.
9. Граф G с петлями и кратными ребрами называется псевдограф. Виды графов
10. Особый интерес представляют связные акциклические графы, называемые деревьями. Дерево на множестве P вершин всегда содержит q=p-1
11. На практике широко используются такие виды графов, как деревья и прадеревья. Деревом называется конечный связный неориентированный
12. Лесом называется несвязный граф, каждая компонента связности которого является деревом. Прадеревом называется ориентированный граф G(X) с
13. Граф G, рёбра которого не имеют определённого направления, называется неориентированным. Неориентированный граф
15. Скачать презентацию

Слайд 2

Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения

всех четырех частей суши в задаче о кенигсбергских мостах (1736)

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

Слайд 3

Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами,

и конечного множества элементов, называемых ребрами.

Основные понятия

Граф G=(V, E)
V={v1, v2, v3, v4, v5} ;
E={e1, e2, e3, e4, e5, e6, e7}

Слайд 4

Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра

ek.
Ребра с одинаковыми концевыми вершинами называются параллельными (e1,e4 ).
Петля– замкнутое ребро(e5).
Ребро, принадлежащее вершине, называется инцидентным (ребро e1 инцидентно вершинам v1 и v2).

Основные понятия

Слайд 5

Изолированная вершина не инцидентна ни одному ребру (v3).
Две вершины смежны, если

они являются концевыми вершинами некоторого ребра (v1, v4).
Если два ребра имеют общую концевую вершину, они называются смежными (e1, e2).

Основные понятия

Слайд 6

Подграф – любая часть графа, сама являющаяся графом.
Основные понятия
Подграф H графа

Слайд 7

Граф G=(V,E) называется простым, если он не содержит петель и параллельных

ребер.

Виды графов

Граф G=(V,E) называется полным, если он простой и каждая пара вершин смежна.

Слайд 8

Виды графов
Ноль-граф - граф, множество ребер которого пусто.
Граф G с кратными

ребрами называется мультиграф.

Слайд 9

Граф G с петлями и кратными ребрами называется псевдограф.
Виды графов

Слайд 10

Особый интерес представляют связные акциклические графы, называемые деревьями. Дерево на множестве

P вершин всегда содержит q=p-1 ребер, т.е. минимальное количество ребер, необходимое для того, чтобы граф был связанным. При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты, каждая из который представляет собой также дерево или изолированную вершину. Несвязанный граф, компоненты которого являются деревьями, называется лесом.

Виды графов

Слайд 11

На практике широко используются такие виды графов, как деревья и прадеревья.
Деревом

называется конечный связный неориентированный граф, состоящий, по крайней мере, из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер
Ветвями дерева называются ребра графа, входящие в дерево. Хордами дерева называются ребра, входящие в граф, дополнительный к данному дереву. Лагранжевым деревом называется дерево, все ветви которого имеют общую вершину.

Виды графов

Слайд 12

Лесом называется несвязный граф, каждая компонента связности которого является деревом.
Прадеревом называется

ориентированный граф G(X) с корнем х0 ∈ X, если в каждую вершину хi ≠ х0 (хi ∈ X) заходит ровно одна дуга, а в корень х0 не заходит ни одна дуга. Прадерево не содержит контуров

Виды графов

Слайд 13

Основные понятия теории графов

Содержание

Основоположником теории графов считается Леонард Эйлер, который доказал невозможность маршрута прохождения

Граф G=(V,E) состоит из двух множеств: конечного множества элементов, называемых вершинами,

Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра

Изолированная вершина не инцидентна ни одному ребру (v3). Две вершины смежны, если

Подграф – любая часть графа, сама являющаяся графом.Основные понятияПодграф H графа

Граф G=(V,E) называется простым, если он не содержит петель и параллельных

Виды графов Ноль-граф - граф, множество ребер которого пусто. Граф G с кратными

Граф G с петлями и кратными ребрами называется псевдограф.Виды графов

Особый интерес представляют связные акциклические графы, называемые деревьями. Дерево на множестве

На практике широко используются такие виды графов, как деревья и прадеревья.Деревом

Лесом называется несвязный граф, каждая компонента связности которого является деревом.Прадеревом называется

Граф G, рёбра которого не имеют определённого направления, называется неориентированным.Неориентированный граф

Похожие презентации

Изолированная вершина не инцидентна ни одному ребру (v3).
Две вершины смежны, если

Подграф – любая часть графа, сама являющаяся графом.
Основные понятия
Подграф H графа

Виды графов
Ноль-граф - граф, множество ребер которого пусто.
Граф G с кратными

Граф G с петлями и кратными ребрами называется псевдограф.
Виды графов

На практике широко используются такие виды графов, как деревья и прадеревья.
Деревом

Лесом называется несвязный граф, каждая компонента связности которого является деревом.
Прадеревом называется

Граф G, рёбра которого не имеют определённого направления, называется неориентированным.
Неориентированный граф