WWW.OS.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Научные публикации
 


«Лекции на сайте Графы Деревья Число висячих вершин Определение графа (Неориентированным) графом G ...»

Лекция: Графы. Основные понятия. Связные

графы. Деревья. Остовное дерево. Число

висячих вершин в остовном дереве.

Лектор - доцент Селезнева Светлана Николаевна

Лекции по “Дискретным моделям”.

Магистратура, 1-й курс,

факультет ВМК МГУ имени М.В. Ломоносова

Лекции на сайте http://mk.cs.msu.su

Графы Деревья Число висячих вершин

Определение графа

(Неориентированным) графом G называется пара (V, E ),

где

V = {v1, v2,..., vp } – множество вершин;

E = {e1, e2,..., eq } – множество ребер, в котором каждое ребро ei есть неупорядоченная пара вершин (vi1, vi2 ), где vi1, vi2 V.

Обозначения:

V (G ) – множество вершин графа G, E (G ) – множество ребер графа G, v (G ) – число вершин в графе G, e(G ) – число ребер в графе G.

Графы Деревья Число висячих вершин Петли и кратные ребра Ребро ei = (vi1, vi1 ) называется петлей.

Ребра ei = (vi1, vi2 ) и ej = (vi1, vi2 ), i = j, называются кратными ребрами.

Как правило, мы будем рассматривать графы без петель и кратных ребер.

Графы Деревья Число висячих вершин Смежность Говорят, что ребро ei = (vi1, vi2 ) соединяет вершины vi1 и vi2, или вершины vi1 и vi2 инцидентны ребру ei.

При этом вершины vi1 и vi2 называются концами ребра ei, или смежными (соседними) по ребру ei.



Графы Деревья Число висячих вершин Степень вершины Степенью dG (v ) вершины v V в графе G = (V, E ) называется число инцидентных ей ребер.

Если dG (v ) = 0, то вершина v называется изолированной в графе G, если dG (v ) = 1, то вершина v называется висячей в графе G.

Обозначения: (G ) = min dG (v ) и (G ) = max dG (v ) – v V (G ) v V (G ) соответственно, минимальная и максимальная степени вершин в графе G.

Теорема 1. 1.

Для каждого графа G = (V, E ) верно, что dG (v ) = 2|E |.

v V

2. В каждом графе число вершин, имеющих нечетную степень, четно.

Графы Деревья Число висячих вершин Диаграмма графа Графы можно изображать в виде диаграмм.

Вершины изображаются точками (или кружочками).

Ребро ei = (vi1, vi2 ) изображается линией, соединяющей вершины (точки) vi1 и vi2.

Пусть G = (V, E ), где V = {1, 2, 3}, E = {e1, e2, e3 }, где e1 = (1, 2), e2 = (1, 2) и e3 = (1, 3).

Графы Деревья Число висячих вершин Диаграмма графа Графы можно изображать в виде диаграмм.

Вершины изображаются точками (или кружочками).

–  –  –

в которой eij = (vij1, vij ) E для каждого j = 1,..., l.

При этом вершина vi0 называется началом маршрута, вершина vil называется концом маршрута. Число l ребер маршрута называется его длиной.

Для графов без петель и кратных ребер маршрут однозначно определяется последовательностью вершин vi0 vi1 vi2... vil1 vil.

Путь – это маршрут без повторений ребер.

Простой путь – это путь без повторений вершин.

Графы Деревья Число висячих вершин Циклы в графе

–  –  –

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

Теорема 4. В каждом связном графе G = (V, E ) найдется остовное дерево.

Доказательство (1-й способ). Если в графе G нет циклов, то он является своим остовным деревом.

Иначе, рассмотрим в графе G цикл. Пусть e – ребро из этого цикла. Повторим рассуждения для графа G e, который, очевидно, также является связным.

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

Графы Деревья Число висячих вершин Остовные деревья

–  –  –

Число остовных деревьев Полный граф, или клика Kn – это граф с n вершинами, в котором любые две вершины соединены ребром.

Теорема 5. В полном графе Kn есть nn2 остовных деревьев.

Доказательство. Пусть V = {1, 2,..., n}.

Для каждого остовного дерева D1 графа Kn построим его код k(D1 ) = (j1,..., jn2 ).

Пусть i1 – это висячая вершина c минимальным номером в дереве D1. Она смежна с единственной вершиной j1.

Повторим рассуждения для дерева D2 = D1 i1 и т.д.

Останавливаемся, когда получим дерево Dn1, являющееся ребром.

Графы Деревья Число висячих вершин Число висячих вершин А сколько висячих вершин может быть в остовном дереве графа G ?

Теорема 6. Для каждого связного графа G можно построить остовное дерево с не менее, чем (G ), висячими вершинами.

Доказательство. Будем строить остовное дерево так: сначала выберем вершину v V, такую, что dG (v ) = (G ), вместе со всеми исходящими из нее ребрами.

Затем будем добавлять к этой звезде ребра графа G так, чтобы не появились циклы. В итоге построим остовное дерево, в котором будет не менее, чем (G ) висячих вершин.

Графы Деревья Число висячих вершин Достижимость числа висячих вершин

–  –  –

Достижимость числа висячих вершин Доказательство (продолжение). Пусть для некоторого k, m k n, в последовательности остовных деревьев нет дерева k висячими вершинами.

Значит, найдутся два соседних дерева Dj и Dj+1, такие, что в дереве Dj – (k 1) висячих вершин, а в дереве Dj+1 – (k + 1) висячих вершин.

Рассмотрим цикл Cj в графе Gj. Концы ребра ej имеют степень больше двух, а концы ребра ej имеют степень два в цикле Cj. Значит, в цикле Cj найдется такое ребро e, что один его конец имеет стень два, а другой его конец имеет степень, большую двух.

Тогда дерево D = Gj e – остовное дерево с j вершинами в графе G.

Графы Деревья Число висячих вершин

Большое число висячих вершин

Теорема 8. В связном графе G c (G ) 3 найдется остовное дерево с не менее, чем v (G )/4 висячими вершинами.

Доказательство. Опишем алгоритм построения такого остовного дерева.

Пусть дерево D – это подграф графа G. Висячую вершину дерева D назовем стабильной, если все смежные ей вершины принадлежат также дереву D.

Обозначим через u(D) число его висячих вершин дерева D, через s(D) – число его стабильных висячих вершин.

Пусть (D) = 3u(D)/4 + s(D)/4 v (D)/4.

Графы Деревья Число висячих вершин



Похожие работы:

«СОГЛАСОВАНО УТВЕРЖДЕНО с Комитетом по аудиту, информации и Правлением ОАО «Корпорация «Иркут» отношениям с акционерами Протокол № 36 от 26 июля 2010 г. Совета директоров ОАО «Корпорация «Иркут» Протокол №1 от 12 апреля 2010 г. ПОЛОЖЕНИЕ О СИСТЕМЕ ВНУТРЕННЕГО КОНТРОЛЯ ЗА ФИНАСОВО-ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТЬЮ ОАО «КОРПОРАЦИЯ «ИРКУТ» Москва 2010 г. 1. Область применения. 1.1.Настоящее Положение устанавливает цели, задачи, структуру и функции основных участников Системы внутреннего контроля за...»

«Что мне пришлось пережить с Германом Стерлиговым 2021 год от Воплощения Христова « » Предисловие.........................................................9 Вступление «Свой дом».............................................11 Часть I. Как я стала миллионершей..................................13 Глава 1. Я тебя люблю...........................»

«Деятельность Службы по экологическому контролю и надзору Калининградской области Служба по экологическому контролю и надзору Калининградской области (далее – Служба) является исполнительным органом государственной власти Калининградской области, осуществляющим функции по контролю и надзору в области охраны окружающей среды (региональному экологическому контролю) и обеспечению соблюдения требований законодательства в области охраны окружающей среды. Служба осуществляет региональный экологический...»

«Красильников Александр Юрьевич ОПРЕДЕЛЕНИЕ ФАКТОРОВ, ОБУСЛАВЛИВАЮЩИХ УРОВЕНЬ ПРОФЕССИОНАЛЬНОЙ КОМПЕТЕНТНОСТИ И ВОЛЕВОЙ УСТОЙЧИВОСТИ ТАМОЖЕННЫХ СЛУЖАЩИХ В данной статье рассмотрены условия определения факторов, обуславливающих уровень профессиональной компетентности и волевой устойчивости таможенных служащих. В работе представлены профессиональные качества, необходимые для формирования у должностных лиц таможенных органов с целью исполнения ими служебных обязанностей. Адрес статьи:...»

«Proceedings of 4th European Business Research Conference 9 10 April 2015, Imperial College, London, UK ISBN: 978-1-922069-72-6 Increased Foreign Commercial Banks and Performance of Domestic Commercial Banks in Uganda Nsambu Kijjambu Frederick* and John Ddumba-Ssentamu** This paper focuses on the effect of increased foreign commercial banks on performance of domestic commercial banks in Uganda over the period 2000-2011. Descriptive statistics were used to analyze banks’ performance trends over...»



 
2016 www.os.x-pdf.ru - «Бесплатная электронная библиотека - Научные публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.