АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Деревья. Лес. Разрезы

Читайте также:
  1. II.Организация проезда студентов и преподавателей на место практики и обратно
  2. Англия.
  3. Атрибуты и свойства материи
  4. Батура, М. П.
  5. Более подробно вопрос об объектах экологических общественных отношений рассмотрен в главе II учебника. 27 страница
  6. Более подробно вопрос об объектах экологических общественных отношений рассмотрен в главе II учебника. 27 страница
  7. Бури, ураганы, циклоны, смерчи
  8. Быт древних славян по филологическим данным
  9. Введение
  10. Введение
  11. ВЕРА В ВИДИМОСТЬ И ЕЕ КРУШЕНИЕ
  12. Виктор Франкл.

 

Связный граф,не содержащий циклов, называется деревом.

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

Кодеревом T* остова T графа G называется такой подграф G, который содержит все его вершины и только те ребра, которые не входят в T. На рисунке 3.6. представлены граф G, его дерево G1 остов T1 и кодерево .

 

G G1

 

 

T1

 

Рис. 3.6

 

Теорема: Граф G с n вершинами является деревом тогда и только тогда, когда G – связный граф и число его рёбер равно (n-1)

Ребра остова T называются ветвями графа G, а ребра кодерева – T*- связями.

 

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

Граф, не содержащий циклов и состоящий из k компонент, называется k -деревом; k - дерево графа G, содержащее все его вершины, называется остовным.

Подграф G, содержащий все его вершины и только те его ребра, которые не входят в остовное k -дерево T графа G, называется k -кодеревом Т*. Если граф G содержит k -компонент, то его остовное k -дерево Т называется ЛЕСОМ, а k -кодерево Т* в этом случае называется КО-ЛЕСОМ.

На рис.3.7 изображены остовное 2 –дерево Т и 2-кодерево Т* графа G, представленного на рис.3.6

 

 

Т Т*

Рис.3.7

 

На рисунке 3.8 изображены граф G,содержащий две компоненты, его лес Т и ко - лес Т*

G (граф)

 

Т (лес)

 

Т* (ко-лес)

 

 

Рис 3.8

Рангом графа G, имеющего n вершины и состоящего из k компонент, называется число

r(G)= n-k (2)

Цикломатическим числом графа G называется число

μ(G)= m-n+k (3)

где m – число рёбер графа G; n – число вершин; k – число компонент

Связь между r и μ: r(G)+ μ(G)=m (4)

 

Теорема. Ранг r(G) графа G равен числу рёбер леса, а цикломатическое число μ(G) равно числу рёбер ко- леса.

Ранг и цикломатическое число являются числовыми характеристиками графа, определяющими размерность подпространств циклов и разрезов.

Пусть есть некоторый связный граф G, множество вершин которого разбито на два непустых непересекающихся подмножества: P=P1 P2. Тогда множество всех рёбер G, имеющих одну концевую вершину в P1, а другую – в P2,называется разрезом графа G.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)