WWW.LIB.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные матриалы
 


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

Лекция 4. Графы.

Основные понятия. Связные

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

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

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

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

Магистратура, 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, число вершин в графе G, v (G ) число ребер в графе G.

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

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

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

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

Графы Деревья Число висячих вершин Задачи Изоморфизм графов Два графа (без петель и кратных ребер) G1 = (V1, E1 ) и G2 = (V2, E2 ) называются изоморфными, если найдется такое взаимно однозначное отображение : V1 V2, что для любой пары вершин v, w V1 верно:

(v, w ) E1 тогда и только тогда, когда ((v ), (w )) E2.

Графы Деревья Число висячих вершин Задачи Смежность Ребро 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).

–  –  –

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

замкнутый маршрут без повторений ребер.

Цикл Простой цикл цикл, в котром все вершины, кроме последней, различны.

Теорема 2. 1.

Из любого замкнутого маршрута нечетной длины m, m 3, можно выделить простой цикл.

2. В любом графе G найдутся простая цепь с длиной, не меньшей (G ) 1, и простой цикл с длиной, не меньшей (G ).

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





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

Теорема 3. Если граф G с p вершинами, q ребрами и s компонентами связности, то s p q, если при этом в графе G отсутствуют циклы, то s = p q.

Теорема 4. 1.

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

2. Если в связном графе удалить ребро из цикла, то останется связный граф.

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

Деревья

связный граф без циклов.

Дерево Теорема 5. 1. Любое дерево с p 2 вершинами содержит хотя бы две висячие вершины.

2. В любом дереве с p вершинами и q ребрами верно q = p 1.

3. В любом дереве любые две вершины соединены ровно одной простой цепью.

4. Если к дереву добавить ребро, соединяющее его несмежные вершины, то появится ровно один цикл.

5. Если из дерева удалить ребро, то останется граф с двумя компонентами свяности.

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

Остовные деревья

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

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

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

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

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

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

–  –  –

Число остовных деревьев Доказательство (продолжение). Пусть получен код k(D1 ) = (j1,..., jn2 ).

Как по нему восстановить дерево D1 ?

Заметим, что если i не содержится в коде k(D1 ), то i висячая вершина дерева D.

Пусть V1 = V. Выбираем наименьший номер i1 из V1, не содержащийся в k(D1 ). Соединяем вершины i1 и j1. Пусть V2 = V1 \ {i1 }.

Повторяем рассуждения для множества V2 и кода (j2,..., jn2 ).

Заметим, что множество Vn1 содержит ровно две вершины.

Их нужно соединить ребром. Получим дерево D1.

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

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

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

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

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

Оценка числа висячих вершин

Теорема 9. В связном графе 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.

Графы Деревья Число висячих вершин Задачи Оценка числа висячих вершин Доказательство (продолжение). Остовное дерево будем строить по индукции.

Базис индукции: выберем в графе G произвольную вершину v.

Пусть D1 эта вершина вместе со всеми исходящими из нее ребрами и их вторыми концами.

Тогда, т.к. dG (v ) 3, верно

–  –  –

Оценка числа висячих вершин Доказательство (продолжение). Пусть уже построено дерево Dj. Пусть W = V (G ) \ V (Dj ).

1. Если в дереве Dj есть невисячая вершина v, смежная с некоторой вершиной w W, то пусть Dj+1 = Dj + (v, w ). Тогда

–  –  –

Оценка числа висячих вершин

4. Иначе, в множестве W есть вершина w, смежная с вершинами дерева Dj. Т.к. п. 3 не выполняется, то вершина w смежна не более, чем с одной вершиной из множества W. Но dG (v ) 3, поэтому вершина w смежна хотя бы с двумя вершинами v, v1 V (Dj ). Пусть Dj+1 = Dj + (v, w ). Т.к.

п.п. 1–2 не выполняются, вершина v1 – висячая в дереве Dj и смежна рово с одной вершиной из множества W, а именно, с вершиной w. Поэтому в дереве Dj+1 висячая вершина v1 устойчивая. Тогда



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

«ОГЛАВЛЕНИЕ 1. ВВЕДЕНИЕ 2. Физические предпосылки для управления оптическими характеристиками 5 3.Процессы изменения валентности ионов Yb3+ в кристаллах Ce3+ + Yb3+:CaF2 4. Выращивание кристаллов CaF2, активированных РЗИ. 4.1. Изготовление образцов для исследований 4.2. Требование к чистоте исходных компонентов 4.3. Синтез исходных компонентов 4.4. Метод выра...»

«Брянская областная научная универсальная библиотека им. Ф.И. Тютчева Отдел краеведческой литературы КАЛЕНДАРЬ ЗНАМЕНАТЕЛЬНЫХ ДАТ ПО БРЯНСКОЙ ОБЛАСТИ НА 2015 ГОД Брянск-2014 г. Календарь знаменательных дат по Брянской области на 2015 год / Брян. обл. науч. универс. бка им. Ф.И. Тютчева, отд. краевед. литературы. – Бр...»

«Утверждена постановлением Администрации Одинцовского муниципального района от "06" октября 2016 г. №5920 МУНИЦИПАЛЬНАЯ ПРОГРАММА ОДИНЦОВСКОГО МУНИЦИПАЛЬНОГО РАЙОНА МОСКОВСКОЙ ОБЛАСТИ "ОХРАНА ОКРУЖАЮЩЕЙ СРЕДЫ В ОДИНЦОВСКОМ МУНИЦИПАЛЬНОМ РАЙОНЕ МОСКОВСКО...»

«И с т О р И Я, А р Х Е О л О Г И Я, Э т Н О Г р А Ф И Я УДК 930(=1.470=511.131)19/20 р. р. Cадиков, т. г. миннияхметова зарубежные иССледователи Этнографии, фольклора и языка закамСкиХ удмуртов: иСториографиЧеСкиЙ оЧерк* В с...»

«ISSN 0131-5226. Теоретический и научно-практический журнал. ИАЭП. 2016. Вып. 90. Работа секции опоросно-подсосной производится в 2 такта. В один такт опоросноподсоная секция с поросятами-отъемышами работает на откормочную секцию 3 (исходную), а во второй такт – на откормочную секцию 5 (дополнтел...»

«ДОКЛАД УПОЛНОМОЧЕННОГО ПО ПРАВАМ ЧЕЛОВЕКА В САНКТ-ПЕТЕРБУРГЕ ЗА 2014 ГОД Уполномоченный Санкт-Петербург по правам человека 2015 в Санкт-Петербурге ДОКЛАД УПОЛНОМОЧЕННОГО ПО ПРАВАМ ЧЕЛОВЕКА В САНКТ-ПЕТЕРБУР...»

«ПРОГРАММА обучающего лагеря для студактива КалмГУ "Навигатор ССУ" Дата проведения: 16 – 18.09.2012 г. Место проведения: РОЛ Целинного района "Сайгачонок". Общее руководство: отдел молодежной политики и внеучебной работы Основные исполнители: студенческий сове...»








 
2017 www.lib.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

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