Главная » Просмотр файлов » XIX Белоусов А.И., Ткачев СБ. Дискретная математика

XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 47

Файл №1081422 XIX Белоусов А.И., Ткачев СБ. Дискретная математика (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска) 47 страницаXIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422) страница 472018-01-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 47)

Кроме того, решение практических задач с помощью матрицы инциденций весьма трудоемко. Оценим, например, временные затраты на решение с помощью матрицы инциденций такой простой задачи в ориентированном графе: для данной вершины оз найти ее „окружение" — множество преемников и множество предтаесптвеиииков вершины оз, т.е. множество всех вершин, непосредственно достижимых из оь, и множество всех вершин, из которых она непосредственно достижима. 290 5. ТЕОРИЯ ГРАФОВ Для решения этой задачи на матрице инциденций ориентированного графа нужно идти по строке с номером Й до появления ненулевого элемента (+1 или -1). В случае если обнаружена +1, в соответствующем столбце надо найти строку, в которой записано число -1.

Номер строки, в которой стоит зто число, дает номер вершины, непосредственно достижимой из данной вершины. Если обнаружена -1, в столбце надо найти строку, в которой записана 1, и получить номер вершины, из которой непосредственно достижима данная вершина.

Для получения всего „окружения" надо проделать указанный поиск для всех ненулевых элементов л-й строки. Наиболее трудоемкой процедурой является поиск ненулевого элемента в столбце. Число таких процедур поиска равно степени вершины еь. Будем в этом случае говорить, что сложность алеорппьма анализа окружения вершины еь составляет 0(йбеь) (порядка йбеь). Можно увидеть, что поиск „окружения" всех вершин займет время порядка произведения числа вершин ориентированного графа на сумму степеней всех вершин, которая, как можно показать, пропорциональна числу дуг ориентированного графа.

Таким образом, сложность алгоритма поиска „окружения" составляет 0(пт), т.е. поиск занимает время порядка произведения числа вершин на число дуг. Более эффективной матричной структурой, представляющей граф, служит матрица смежностпп еершпи, или 69- лева матпрпца графа. Это квадратная матрица В порядка и, элементы которой определяют следующим образом: для неориентированного графа / 1, 1-я и у-я вершины смеэснме; ~~ О, иначе; для ориентированного графа 1, из 1-й вершины в у-ю ведет дуга; Ф О, иначе.

1 5.2. Свособм предствввеввв 291 Заметим, что в Й-й строке матрицы ориентированного грз фа количество единиц равно полустпеаени исхода дб+ еь вершины еь, а количество единиц в и-м столбце — полусшепени захода дк-ъ~. Длл неориентированного графа маптрина смежности вершин стыьиетпр иве скал. Для ориентированного графа, изображенного на рис.

5.8, матрица смежности вершин имеет вид (о о о). Рассмотрим решение задачи поиска „окружения" с использованием матрицы смежности вершин. Для определения „окружения" вершины еь нужно сначала идти по Й-й строке матрицы и искать ненулевые элементы. Если элемент аы = 1, то вершина сч достижима из вершины еь. После просмотра х-й строки надо просмотреть й-й столбец. Если элемент а ь = 1, то вершина тол достижима ю вершины еу. Можно показать, что с использованием матрицы смежности вершин решение задачи поиска „окружения" всех вершин ориентированного графа будет иметь сложность порядка пз, что эффективнее предыдущей оценки ппт, если число дуг ориентированного графа превьппает число его вершин, а это часто бывает в практических задачах.

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

в ходе решения задачи меняется множество вершин и множество ребер (или дуг). В этом случае эффективным способом машинного представления графа явлшотся списки свтежностпи (или списки инцидентттностпи). Рассмотрим ориентированный граф. Для задания множества вершин, непосредственно достижимых ю вершины е, ис- 292 5. 'ГЕОРИЯ ГРАФОВ пользуют линейный однонаправленный список*. Каждый элемент такого списка включает данные (например, некоторое число) и указатель на следующий элемент списка. Список в целом задается указателем на его первый элемент (голову списка).

Последний элемент списка содержит „пустой" указатель (рис. 5.11). Рис. б.11 Задать для вершины е ее список смежности означает,в произвольном порядке поместить в данные элементов списка номера вершин н, для которых в ориентированном графе есть дуга из и в и (с -+ и). Список смежноспэи вершины п обозначают Ь(е). Отметим, что список смежности вершины может при необходимости дополняться. Для этого в последнем элементе списка „пустой" указатель заменяется указателем на добавляемый элемент, который становится последним элементом списка с „пустым" указателем.

Если количество вершин ориентированного графа известно заранее, то ориентированный граф удобно задавать в виде структуры, называемой масснеоле лидеров. Под масснволемы понимаем матрицу-столбец, элементами которой могут быть некоторые объекты (например, элементы списка смежности). Их называют злемектпами массива. Число элементов массива лидеров равно числу вершин графа. Элементами массива лидеров являются первые элементы списков смежности вершин ориентированного графа.

Пример представления ориентированного графа списками смежности, собранными в массив лидеров, представлен на рис. 5.12. 'Подробное описание обработки списков и всей „программистской" терминологии, испольэованиой в этом абзаце, см:. Варил Н. 293 5.2. Способьг лредстввлеиия Рис. 5.12 С использованием списков смежности совсем просто решается задача поиска преемников данной вершины: для этого достаточно просмотреть список смежности вершины, затратив на это время, пропорциональное ее полусшепеви исхода. Тогда на решение этой задачи для всего ориентированного графа потребуется время порядка числа его дуг. Менее эффективно решается задача поиска предшественников вершины, так как в этом случае необходимо, вообще говоря, просмотреть списки смежности всех вершин с целью поиска в них данной вершины.

Таким образом, задача поиска „окружения" с использованием списков смежности является более трудоемкой, чем в случае использования матриц. Однако удобство динамического формирования описания ориентированного графа в данном случае перевешивает. Если задача поиска предшественников возникает часто, можно использовать двусторонние списки смежности, сопоставляя каждой вершине уже два списка — преемников и предшественников. Описанные способы представления графа списками не исчерцывают всех возможных вариантов, и в литературе по программированию можно найти разнообразные варианты ор- 294 5. ТЕОРИЯ ГРАФОВ ганизации списков.

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

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

На решение задачи поиска „окружения" для всего неориентированного графа потребуется время, пропорциональное произведению числа вершин графа на число его ребер. В заключение рассмотрим еще одну матрицу, характервзующую граф, — так называемую матприцу достпижимостпи. Это квадратная матрица С порядка ~Ц, каждый элемент с;. которой равен 1, если у-я вершина досшиэсима из 1-й вершины, и равен 0 если иначе. Отметим, что, согласно определению достижимости, элементы сч = 1. Метод вычисления матрицы достижимости ориентированного графа по его матрице смежности будет рассмотрен в 5.6. Матрица достижимости несет очень важную информацию об ориентированном графе. Ее аналвз позволяет, например, найти его бвкомиоиеяшы и компоиеяшы.

По определению, в бикомпоненту входят взаимно достижимые вершины. Для двух таких вершин с номерами 1 и у должно выполняться равенство су = с; = 1. Поэтому, чтобы найти бикомпоненту, в которую входит 4-я вершина ориентированного графа, нужно просмотреть 1-ю строку и 1-й столбец матрицы достижимости С и сформировать множество Р, = 1р: с;р — — с,я — — Ц номеров вершин, порождающих искомую 5.2.

Способы представлеппп 295 бикомпоненту. Иэ определения матрицы достижимости вытекает, что в Р; содержатся номера всех вершин данной бикомпоненты. Поскольку две различные бикомпоненты не пересекаютсл, вершины с номерами из множества Р1 при поиске других бикомпонент из рассмотрения можно исключить. Процесс поиска целесообразно начать с первой вершины. Он закончится, когда для каждой вершины будет найдена содержащая ее бикомпонента. При этом может оказаться, что некоторые (а может быть, и все) бикомпоненты содержат только по одной вершине, поскольку каждая вершина, по определению, достижима сама из себя.

Поиск компонент ориентированного графа сложнее, так как в компоненту входят вершины с номерами 4 и у, для которых с;. = 1 или с., = 1. Кроме того, одна и та же вершина может входить в несколько различных компонент. Отметим, что любая бикомпонента или не пересекается с некоторой компонентой, или целиком в нее входит. Мы не будем приводить общий алгоритм поиска компонент, а рассмотрим его на примере. Пример 5.6, Для ориентированного графа, изображенного на рис. 5.9, имеем матрицу достижимости 1 1 1 1 1 О О О 1 1 1 1 О О О 1 1 1 1 О О О О О 1 1 О О О О О 1 1 О О О О О 1 1 1 1 О О О 1 1 1 1 Начнем с поиска бикомпонент. Для первой вершины множе.

ство Р1 = (1) включает только ее саму. Для второй вершины имеем Рз = (2, 3), для четвертой — Р4 = (4, 5) и для шестой— Ре = (6, 7). Соответственно полученные множества вершин порождают бикомпоненты В1, Вэ, Вз и В4, изображенные на рис. 5.9. 296 5. 7ЕОРИЯ ГРАФОВ Перейдем к поиску компонент. Используя матрицу С, выпишем для каждой вершины е;, 4 = 1, 7, множество К;, состоящее иэ тех вершин, которые достижимы из 4-й вершины или из которых достижима она. В рассматриваемом ориентированном графе для вершины е7 в множество К7 входят вершины, для которых с77 = 1 или си = = 1, т.е. К7 = (о1 е2 ез е4 эбан.

Для вершин е2 и ЮЗ множества К2 и Кз совпадают с множеством К7. Поскольку все элементы четвертого и пятого столбцов матрицы С равны единице, то для вершин еб и еб имеем К4 =Кб = (выпэ,ез,е4,еб,еб,е71. Для верп7ин еб н с7 получим Кб = К7 = 1е4) об~ еб) ю71. Отметим, что множество К; построено так, что любая компонента, содержащая вершину о;, может содержать только вершины из множества К;. Кроме того, если некоторая компонента Ср содержит вершины е, и е., то вершина е,„будет принадлежать этой компоненте в том и только в том случае, если е,в Е К; й К7.

Характеристики

Тип файла
DJVU-файл
Размер
5,42 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Зарубин В.С., Крищенко А.П
Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее