рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Остовы графов

Реферат Курсовая Конспект

Выберите учебное заведение

Остовы графов

Остовы графов - раздел Математика, Остовы графов Деревом Называется Связный Неорграф, Не Содержащий Циклов. Любой Неорграф Без...

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

ТеоремаДля неорграфа G без петель, содержащего n вершин, следующие условия эквиваленты:

1) G-дерево;

2) G-связный граф, содержащий n-1 ребро;

3) G-ациклический граф, содержащий n-1 ребро;

4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;

5) G- ациклический граф, такой, что если какую-нибудь пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

Пусть G=‹M;R›- неорграф. Часть G΄=‹M̕;R΄› графа G называется остовом или каркасом графа G, если M=M̕ и G΄-лес, который на любой связной компоненте графа G образует дерево. Таким образом, если G-связный граф, то остов G̕ является деревом, которое будем называть остовным деревом графа G.

Понятие остова для ортграфа G определяется как часть G̕ графа G, для которой F(G̕) является остовом графа F(G). Аналогично вводится понятие остовного дерева для связного орграфа G.

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

П р и м е р. В качестве остова графа, G изображенного ниже, можно взять лес с ребрами 2,3,4,6,7 (вообще говоря, остов определяется неоднозначно).

2 3 4

6 7

5 8

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Остовы графов

тема quot Элементы теории графов Виды и способы задания графов quot... Даны населенные пункты расстояния между которыми известны Требуется найти маршрут проходящий через все пункты по...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Остовы графов

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Упорядоченные и бинарные деревья
Определим по индукции понятие упорядоченного дерева: 1) пустое множество и список (a), где a-некоторый элемент, является упорядоченным деревом; 2) если T₁,T₂, …

Фундаментальные циклы
Пусть G= неорграф, имеющий n вершин, m ребер и с компонент связности, T-остов графа G. В §4.8 отмечалось, что T имеет v*(G)=n-c ребер u1, … , un-c, котор

Разрезы
Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи возникают, например, при изучении потоков в сетях (сетью

Связанные с графами
Рассмотрим алгебраическую систему 2= с двухместными операциями кольцевого сложения ⊕ и умножения ⊙, задаваемыми следующими правилами: 0⊕0=1⊕1=0, 1

Раскраски графов
Пусть G= неорграф без петель. Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если ребро, то вершины и имеют различные цвета. Хроматически

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

Задачи и упражнения
1. Представить граф ( рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности. 2. Составить матрицу инцидентичности для мультиграфа, изображенного