Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Пример 3. Определение. Маршрутом длины на графе называется такая последовательность


Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

3.2. Маршруты, цепи и циклы в графе

Определение. Маршрутом длины на графе называется такая последовательность вершин и ребер графа, в которой .

Такой маршрут кратко называют -маршрутом и кратко обозначают . Про -маршрут говорят, что он соединяет вершину с вершиной . Вершины и называют соответственно началом и концом маршрута.

Случай, когда длина маршрута равна нулю, не исключается; в этом случае маршрут сводится к одной вершине.

Если ,то маршрут называется замкнутым.

Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью своих вершин.

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

Определение. Цепь – это маршрут без повторяющихся ребер.

Цепь, соединяющую вершину с вершиной , кратко называют -цепью и обозначают .

Определение. Цепь называется простой, если в ней нет повторяющихся вершин за исключением, быть может, совпадающих концевых.

Определение. Замкнутая цепь называется циклом.

Определение. Замкнутая простая цепь называется простым циклом.

Пример 1. - -маршрут; его длина равна 4; данный маршрут является -цепью; эта цепь незамкнутая, не простая. Маршрут - цикл длины 5, этот цикл не является простым; - простой цикл.

 

 

3.3. Связность, компоненты связности графа

Определение. Обозначим через Gi подграф графа G, порожденный множеством вершин Vi . При этом

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

Определение. Число различных компонент связности графа называется числом связности и обозначается .

Определение. Если , то граф называется связным.

Пример 1. Рассмотрим граф , с множеством вершин , множеством ребер и отображением инцидентности: , , , . Имеем три компоненты связности:

1. , где , , , , ;

2. , где , ;

3. , где , , .

 

3.4. Цикломатическое число графа

Пусть - произвольный граф; - число его вершин, - число ребер, - число связности.



Определение. Поставим графу в соответствие число , называемое цикломатическим числом графа.

3.5. Матрицы, ассоциированные с графом

Во многих задачах теории графов (особенно реализуемых на ЭВМ) графы удобно описывать матрицами. Пусть - произвольный неориентированный граф с m вершинами и n ребрами. Занумеруем вершины графа.

Определение. Матрицей смежности неориентированного графа называется матрица размера , элементы которой , где - число ребер, соединяющих вершины с номерами , причем при каждую петлю учитываем дважды.

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

Помимо вершин занумеруем ребра графа.

Определение. Матрицей инцидентности неориентированного графа называется матрица размера , элементы которой определены следующим:

1. , если вершина с номером i инцидентна ребру с номером j и j-ое ребро не является петлей;

2. во всех остальных случаях.

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

Пример.; .

 

3.6. Деревья и леса

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

Определение. Связный ациклический граф называется деревом.

Каждая компонента связности леса – дерево, следовательно, для -связного леса существует дизъюнктное разбиение на деревьев.

Пример 1. Граф не является деревом, не является лесом. Граф - дерево. Граф - лес.

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

Следствие. Если граф --связный лес, то .

<== предыдущая лекция | следующая лекция ==>
Пример 3. Заметим, что степень каждой вершины полного графа равна , так что | Кодирование деревьев

Дата добавления: 2014-01-03; Просмотров: 409; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:

  1. В качестве примера формирования приусадебного землепользования рассмотрим следующую ситуацию.
  2. В социальной самоидентификации играют роль запахи, обусловленные генотипом и средовыми влияниями, например диетой.
  3. Величина среднесуточной предельно допустимой концентрации строже, жестче, чем максимально-разовая ПДК, и составляет примерно 10% от величины последней.
  4. Власть примера. Влияние с помощью харизмы.
  5. Внимание: не брать из интернета и из лекции. Другие примеры.
  6. ВОПРОС 4. ПРИМЕРЫ ПРАКТИЧЕСКОГО ИСПОЛЬЗОВАНИЯ ОСНОВНОГО УРАВНЕНИЯ ГИДРОСТАТИКИ
  7. Вопрос Государственная система управления информационной безопасностью в РФ(на примере ФТС)
  8. Г.Ф. Шершеневич, например, пишет: «Различные формы, в которых выражается право, носят издавна название источников права».
  9. ГОСТ12.Х.ХХХ-ХХ ССБТ. (Например, ГОСТ12.1.005-88),
  10. Для примера 1.
  11. Зовании (например, в агрессивной среде).
  12. И их примерные типовые социальные группировки

studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.031 сек.