WWW.NEW.PDFM.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Собрание документов
 

«транспорта светофором. Графовая модель управления светофором на перекрестке. Лектор - доцент Селезнева Светлана Николаевна Лекции по “Дискретным моделям”. Магистратура, 1-й курс, факультет ...»

Лекция: Графы интервалов. Применения графов

интервалов. Задача регулирования движения

транспорта светофором. Графовая модель

управления светофором на перекрестке .

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

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

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

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

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

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором

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

Граф (неориентированный) G = (V, E ) называется графом интервалов, если каждой вершине v V можно поставить в соответствие такой отрезок действительной оси J(vi ) = [ai ; bi ], ai, bi R, ai bi, что (vi1, vi2 ) E J(vi1 ) J(vi2 ) = 0 .

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

Если G = (V, E ) – граф интервалов, то семейство J(G ) = {J(v ) | v V } отрезков, сопоставленных его вершинам, будем называть интервальным представлением этого графа .

Для одного и того же интервального графа существует множество его интервальных представлений .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Интервальность полного графа на трех вершинах Пример 1. 1. Граф K3 = ({1, 2, 3}; {(1, 2), (2, 3), (3, 1)}} – полный граф на трех вершинах – является интервальным .

Например, его интервальным представлением является семейство J(K3 ) : {J(1) = [0; 1, 5], J(2) = [0, 5; 2], J(3) = [1; 2, 5] } Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Неинтервальность цикла на четырех вершинах Пример 1 (продолжение). 2. Граф Z4 = ({1, 2, 3, 4}; {(1, 2), (2, 3), (3, 4), (4, 1)}} – цикл на четырех вершинах – не является интервальным .



Докажем неинтервальность графа Z4 от противного: пусть найдется его интервальное представление J(1) = [a1 ; b1 ]; J(2) = [a2 ; b2 ];

J(Z4 ) :

J(3) = [a3 ; b3 ]; J(4) = [a4 ; b4 ] .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Неинтервальность цикла на четырех вершинах Пример 1 (продолжение). 2. Т.к. (1, 2) E, отрезки J(1) и J(2) пересекаются. Пусть, для определенности, отрезок J(2) лежит правее отрезка J(1), т.е. a1 a2 .

Т.к. (2, 3) E, а (1, 3) E, отрезки J(2) и J(3) пересекаются, а / отрезки J(1) и J(3) не пересекаются. Т.е. a3 b2 и b1 a3 .

Т.к. (2, 4) E, отрезки J(2) и J(4) не пересекаются. Т.е .

/ отрезок J(4) лежит правее отрезка J(2), и b2 a4 .

Получили, что b1 a3, a3 b2 и b2 a4. Т.е. b1 a4 – отрезки J(1) и J(4) не пересекаются .

Пришли к противоречию, т.к. (4, 1) E .

Значит, предположение о том, что Z4 – интервальный граф неверно .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Применение графов интервалов Графы интервалов рассматривались для построения моделей в биологии – при построения модели ДНК – участки ДНК, за которые отвечают разные гены могут пересекаться;

в археологии – при восстановлении хронологического порядка археологических находок – физические (радиоуглеродный и др.) методы дают отрезок времени, к которому могут находки принадлежать, отрезки могут пересекаться;

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

И т.д .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Полные графы Нас будет интересовать критерий того, что заданный граф G = (V, E ) является интервальным .





Для формулировки критерия нам понадобятся понятия полного графа и клики в графе Граф Kn = (V, E ), |V | = n, E = {(v1, v2 ) | v1, v2 V, v1 = v2 }, называется полным графом на n вершинах .

Т.е. в полном графе любые две различные вершины соединены ребром .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Клики в графе Граф G = (V, E ) называется подграфом графа G = (V, E ), если V V, E E .

Кликой в графе называется его подграф, являющийся полным графом .

Клика называется максимальной, если она не содержится в большей клике .

Например, в графе G клики K1 = {1, 2} и K2 = {2, 3, 4} – максимальны, а клика K = {3, 4} – нет .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Максимальные клики в графе

–  –  –

Свойства максимальных клик

3) Если (u, v ) E, то найдется максимальная такая клика K, что u, v K .

Доказательство п. 3). Ребро (u, v ) является кликой в графе G .

Если она не максимальна, расширим ее до максимальной клики K. По построению u, v K .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Множество максимальных клик графа Обозначим множество всех максимальных клик графа G через K (G ) .

Из п. 3 теоремы 1 следует, что число максимальных клик в графе G = (V, E ) не превосходит числа его ребер, т.е .

|K (G )| |E | .

Заметим, что клики в множестве K (G ) могут пересекаться .

Например, для графа G множество его максимальных клик K (G ) = {K1 = {1, 2}, K2 = {2, 3, 4}, K3 = {4, 5}} .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором

–  –  –

Критерий интервальности графа Теперь у нас все готово, чтобы сформулировать критерий Фалкерсона-Гросса интервальности графа .

Теорема 2 [Фалкерсона-Гросса]. Пусть G = (V, E ) – граф .

Граф G является интервальным тогда и только тогда когда найдется последовательное упорядочение максимальных клик из множества K (G ) .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором

Алгоритм построения интервального представленияграфа

Пусть G = (V, E ) – граф, K (G ) – множество его максимальных клик, и K1, K2,..., Kp последовательное упорядочение всех клик из множества K (G ) .

Шаг 1. Для каждой вершины u V построим множество J (u) = {Ki K (G ) | u Ki }, т.е. множество всех максимальных клик, содержащих вершину u .

Шаг 2. Для каждой вершины u V отрезок J(u), сопоставляемый вершине u, получаем как минимальный отрезок действительной оси, содержащий все индексы клик из множества J (u) .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Пример Пример 2. Рассмотрим граф G, изображенный на рисунке, и K (G ) = {K1 = {1, 2}, K2 = {2, 3, 4}, K3 = {4, 5}} множество его максимальных клик в их последовательном упорядочении .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором

–  –  –

Обобщения интервальных графов Можно рассматривать другие виды интервальных графов и их обобщений .

Например, вершины можно отображать на единичные отрезки или на дуги окружности .

Далее мы рассмотрим применения графов дуг окружности на примере задачи регулирования движения транспорта светофором .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Регулирование движения на перекрестке Рассмотрим задачу управления фазами включения светофора для регулирования движения транспорта на сложном перекрестке. Соотнесем каждому транспортному направлению (дороге, пешеходному переходу и т.д.) отрезок времени, в течение которого горит зеленый свет .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором

Содержательное описание задачи

Рассмотрим простейший случай светофора только с зеленым и красным светом .

Представим круглые часы, и поставим в соответствие отрезку зеленого света транспортного направления u дугу J(u) на окружности этих часов .

Ясно, что некоторые направления совместимы .

Среди них те, которые не приводят к столкновению (не пересекаются); или те, для которых одновременное движение в обоих направлениях не слишком рискованно и не явится причиной задержек .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Совместимые и несовместимые направления движения Например, на рисунке поток транспорта A совместим с потоком B, но не совместим с потоком C .

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

Принимаем утверждение:

1) если два направления движения совместимы, то разрешается перекрытие дуг, соответствующих зеленому свету .

2) если два направления движения не совместимы, то не допускается перекрытие дуг, соответствующих зеленому свету .

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

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором

Графовая модель управления светофором

Построим графовую модель нашей задачи .

Для перекрестка определим граф соответствий G () = (V (), E ()), где V () – множество направлений движения;

(u, v ) E (), где u, v V (), в том и только в том случае, когда направления движения u и v совместимы .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Граф сответствий перекрестка Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Приближенное решение задачи Построив интервальное представление полученного графа соответствий перекрестка, мы построим управление этого перекрестка светофором .

Однако не каждый граф является графом интервалов .

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

А затем находим интервальное представление для этого интервального его подграфа .

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

А потом для каждой цепи строить ее интервальное представление .

Напомним, что граф C = (V (C ), E (C )) называется цепью длины p, если

–  –  –

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

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Пример разбиения на цепи подграфа Например, граф H() является подграфом графа G (), и он разбивается на непересекающиеся цепи .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Решение задачи управления светофором Пусть G () – граф соответствий перекрестка, а H() – его подграф, который разбит на непересекающиеся цепи .

Тогда решение задачи об управлении светофором состоит в нахождении интервального представления (на окружности) графа H() .

А для этого можно воспользоваться алгоритмом нахождения интервального представления графа .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Нахождение интервального представления для подграфа графа перекрестка Рассмотрим последовательное упорядочение максимальных клик графа H():

K1 = {A, B}, K2 = {C, D}, K3 = {D, F }, K4 = {F, E } .

Тогда J (A) = J (B) = {K1 }, J (C ) = {K2 }, J (D) = {K2, K3 }, J (F ) = {K3, K4 }, J (E ) = {K4 } .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Нахождение интервального представления для подграфа графа перекрестка

Откуда получаем интервальное представление графа H():

J (A) = J (B) = [1; 1], J (C ) = [2; 2], J (D) = [2; 3], J (F ) = [3; 4], J (E ) = [4; 4] .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Преключения света в светофоре

Нашли регулирование сигналов светофора на перекрестке:

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Задачи для самостоятельного решения

1. При помощи интервального представления графов построить управление сигналами светофора на перекрестке, на котором направления B и C, B и D, C и E не могут пересекаться (см .

рисунок на следующейц странице) .

1) Построить граф соответствий перекрестка .

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

3) Считая, что минимальный интервал зеленого сигнала светофора равен 10 с, описать временной цикл сигналов этого светофора .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Задачи для самостоятельного решения Графы интервалов Применение Клики Задача регулирования движения транспорта светофором Для самостоятельной работы

1. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986 .

Графы интервалов Применение Клики Задача регулирования движения транспорта светофором

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

«4. СЛУХОВАЯ СИСТЕМА NOCTUOIDEA В начале прошлого века вышла классическая работа Ф. Эггерса (Eggers, 1919) с подробным описанием морфологии тимпанального органа совок (Noctuidae). Затем, спустя 30 лет, появились первые данные, что ноктуиды способны воспринимать ультразвуки (Schaller, Timm, 1950). Дальнейшее систематическое изу...»

«Памяти двух женщин, к которым применимы слова Рамакришны: Мужчина не может осуществить себя, если у него не было замечательной матери и замечательной жены. СЕРДЦЕ АЛЕКСАНДР ГИНГЕР СЕРДЦЕ С т И хи 1917—1964 ПАРИЖ Элегическое двустишие Будешь ты помнить подругу, которой на память дарил ты; скоро забудешь о той, чьи засушил ты цветы....»

«Л. Б. С В Е Т Л О В ПЕРВОЕ ИЗДАНИЕ РУССКОГО ПЕРЕВОДА "ПОХВАЛЫ ГЛУПОСТИ" ЭРАЗМА РОТТЕРДАМСКОГО Первые русские переводы всемирно известного философского, антиклерикального памфлета Эразма Роттердамского "Похва­ ла глупости" относя...»

«Комплекты охранных сигнализаций Ajax Комплект GSM сигнализации GC-101 MINIKIT: Инструкция пользователя AJAX GC – 101 Minikit Руководство по эксплуатации Содержание 1. ОБ УСТРОЙСТВЕ5 2. ОСНОВНЫЕ ВОЗМОЖНОСТИ СИСТЕМЫ7 3. ОСНОВНЫЕ ТЕРМИНЫ УПОТРЕБЛЯЕМЫЕ В РУКОВОДСТВЕ П...»

«Инструкция к муз центру 25-03-2016 1 Изменявшие устои будут подвергать, в случае когда провисающая принудительность увлажнилась . Выносное награмождение чавкает. Ин-кварто плавающий пятерочник в сочетании с валовой — заносящее внесение. Премного показавшаяся сформированность будет...»

«УТВЕРЖДЕНО: Заседание профсоюзного комитета Протокол №_ от "" _ 2014 г. Председатель _А.Е. Прокопович Положение о проведении открытого турнира по спортивной мафии среди студентов-членов ППОС КГПУ им. В.П. Астафьева 1. ЦЕЛИ И ЗАДАЧИ ТУРНИРА 1.1. Содействие успешной адаптации студентов к внеучебной жизни университета.1.2.Формирование условий для...»

«УПРАВЛЕНИЕ ФЕДЕРАЛЬНОЙ НАЛОГОВОЙ СЛУЖБЫ ПО Г. МОСКВЕ НЕ СОГЛАСНЫ С НАЧИСЛЕННЫМ НАЛОГОМ ПО КВАРТИРЕ, АВТОМОБИЛЮ, ЗЕМЕЛЬНОМУ УЧАСТКУ – ОБРАЩАЙТЕСЬ В ИНСПЕКЦИЮ Уважаемые налогоплательщики! Вместе с налоговым уведомлением и платежными документами на уплату нало...»






 
2018 www.new.pdfm.ru - «Бесплатная электронная библиотека - собрание документов»

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