Прикладная математика
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.00 (1 Голос)

Понятие теории графов

пример графа

Понятие теории графов

Важными понятиями теории графов являются понятия дерева и прадерева. Неориентированный связный граф без циклов, имеющий не менее двух вершин, называется деревом. Ориентированный граф G(X,U) называется прадеревом с корнем x1∈ X, если:

1. в каждую вершину xi≠x1 заходит ровно одна дуга;

2. в x1 не заходит ни одна дуга;

3. граф G(X,U) не содержит контуров.

Относительно деревьев можно доказать следующие простые утверждения:

1. Всякая пара вершин в дереве соединена цепью и притом только одной.

Действительно, так как дерево – связный граф, то хотя бы одна цепь существует. Но если бы их было две, то они образовали бы цикл, а дерево не имеет циклов.

2. Удаление любого ребра делает дерево несвязным, причем образуются две компоненты связности.

3. Дерево с n вершинами имеет n-1 ребро. Вершина Xграфа G называется висячей, если в G существует единственное ребро, инцидентное .

Скачать Понятие теории графов в Word

Понятие теории графов - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

По темам:

Google