ЛЕКЦИЯ № 10. Графы

1. Понятие графа. Способы представления графа

Граф - пара G = (V,E), где V - множество объектов произвольной природы, называемых вершинами, а Е - семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство Е могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и Е конечны. Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным, сокращенно - орграф, иначе - неориентированным. Ребра орграфа называются дугами. В дальнейшем будем считать, что термин "граф", применяемый без уточнений (ориентированный или неориентированный), обозначает неориентированный граф.

Если е = <u,v>, то вершины v и и называются концами ребра. При этом говорят, что ребро е является смежным (инцидентным) каждой из вершин v и и. Вершины v и и также называются смежными (инцидентными). В общем случае допускаются ребра вида е = <v, v>; такие ребра называются петлями.

Степень вершины графа - это число ребер, инцидентных данной вершине, причем петли учитываются дважды. Поскольку каждое ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна удвоенному количеству ребер: Sum(deg(vi), i=1...|V|) = 2 * |E|.

Вес вершины - число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.). Вес, длина ребра - число или несколько чисел, которые интерпретируются как длина, пропускная способность и т. д.

Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг - в орграфе) вида v0, (v0,v1), v1..., (vn - 1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин - простой цепью. Путь может быть замкнутым (v0 = vn). Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом.

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

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

1. Матрица инцидентности.

Это прямоугольная матрица размерности n x щ, где n - количество вершин, am - количество ребер. Значения элементов матрицы определяются следующим образом: если ребро xi и вершина vj инцидентны, то значение соотвествующего элемента матрицы равно единице, в противном случае значение равно нулю. Для ориентированных графов матрица инцидентности строится по следующему принципу: значение элемента равно - 1, если ребро xi исходит из вершины vj, равно 1, если ребро xi заходит в вершину vj, и равно О в противном случае.

2. Матрица смежности.

Это квадратная матрица размерности n x n, где n - количество вершин. Если вершины vi и vj смежны, т. е. если существует ребро, их соединяющее, то соответствующий элемент матрицы равен единице, в противном случае он равен нулю. Правила построения данной матрицы для ориентированного и неориентированного графов не отличаются. Матрица смежности более компактна, чем матрица инцидентности. Следует заметить, что эта матрица также сильно разрежена, однако в случае неориентированного графа она является симметричной относительно главной диагонали, поэтому можно хранить не всю матрицу, а только ее половину (треугольную матрицу).

3. Список смежности (инцидентности).

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

Список смежности более эффективен по сравнению с матрицей смежности, так как исключает хранение нулевых элементов.

4. Список списков.

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

2. Представление графа списком инцидентности. Алгоритм обхода графа в глубину

Для реализации графа в виде списка инцидентности можно использовать следующий тип:

Type List = ^S;

end;

Тогда граф задается следующим образом:

Var Gr : array[1..n] of List;

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

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

На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:

Procedure Obhod(gr : Graph; k : Byte);

End;

Примечание

В данной процедуре при описании типа Graph имелось в виду описание графа списком списков. Массив nov[i] - специальный массив, i-ый элемент которого равен True, если i-ая вершина не просмотрена, и False - в противном случае.

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

3. Представление графа списком списков. Алгоритм обхода графа в ширину

Граф можно определить с помощью списка списков следующим образом:

Type List = ^Tlist;

end;

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

Приведем процедуру обхода графа в ширину на псевдокоде:

Procedure Obhod2(v);

End;

Автор: Цветкова А.В.

<< Назад: Графы (Понятие графа. Способы представления графа. Представление графа списком инцидентности. Алгоритм обхода графа в глубину. Представление графа списком списков. Алгоритм обхода графа в ширину)

>> Вперед: Методы (Методы. Конструкторы и деструкторы. Деструкторы. Виртуальные методы. Поля данных объекта и формальные параметры метода)

Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:

▪ Нормальная анатомия человека. Шпаргалка

▪ Травматология и ортопедия. Шпаргалка

▪ Русская литература XX века в кратком изложении. Шпаргалка

Смотрите другие статьи раздела Конспекты лекций, шпаргалки.

Читайте и пишите полезные комментарии к этой статье.

<< Назад

Последние новости науки и техники, новинки электроники:

Питомцы как стимулятор разума 06.10.2025

Помимо эмоциональной поддержки, домашние питомцы могут оказывать заметное воздействие на когнитивные процессы, особенно у пожилых людей. Новое масштабное исследование показало, что общение с кошками и собаками не просто улучшает настроение - оно действительно способствует замедлению возрастного снижения умственных способностей. Работа проводилась в рамках проекта Survey of Health, Ageing and Retirement in Europe (SHARE), охватывающего период с 2004 по 2022 год. В исследовании приняли участие тысячи европейцев старше 50 лет. Анализ показал, что владельцы домашних животных демонстрируют более устойчивые когнитивные функции по сравнению с теми, кто не держит питомцев. Особенно выражен эффект оказался у владельцев кошек и собак. Согласно данным ученых, владельцы собак дольше сохраняют хорошую память, в то время как хозяева кошек медленнее теряют способность к быстрому речевому взаимодействию. Исследователи связывают это с тем, что ежедневное взаимодействие с животными требует внимани ...>>

Мини-ПК ExpertCenter PN54-S1 06.10.2025

Компания ASUSTeK Computer презентовала новый мини-компьютер ASUS ExpertCenter PN54-S1. Устройство ориентировано на пользователей, которым важно сочетание производительности, энергоэффективности и универсальности - от офисных задач до мультимедийных проектов. В основе ExpertCenter PN54-S1 лежит современная аппаратная платформа AMD Hawk Point, использующая архитектуру Zen 4. Это поколение чипов отличается улучшенным управлением энергопотреблением и повышенной вычислительной мощностью. Новинка доступна в конфигурациях с процессорами Ryzen 7260, Ryzen 5220 и Ryzen 5210, представленных AMD в начале 2025 года. Таким образом, устройство охватывает широкий диапазон задач - от базовых офисных до ресурсоемких вычислений. Корпус мини-ПК выполнен из прочного алюминия и имеет размеры 130&#215;130&#215;34 мм, что делает его практически незаметным на рабочем столе или за монитором. Несмотря на компактность, внутренняя компоновка позволяет установить два модуля оперативной памяти SO-DIMM ...>>

Глазные капли, возвращающие молодость зрению 05.10.2025

С возрастом человеческий глаз постепенно теряет способность четко видеть на близком расстоянии - развивается пресбиопия, или возрастная дальнозоркость. Этот естественный процесс связан с утратой эластичности хрусталика и ослаблением цилиарной мышцы, отвечающей за фокусировку. Миллионы людей по всему миру сталкиваются с необходимостью носить очки для чтения или прибегают к хирургическим методам коррекции. Однако исследователи из Центра передовых исследований пресбиопии в Буэнос-Айресе представили решение, которое может стать удобной и неинвазивной альтернативой - специальные глазные капли, способные улучшать зрение на длительный срок. Разработку возглавила Джованна Беноцци, директор Центра. По ее словам, цель исследования состояла в том, чтобы предоставить пациентам с пресбиопией эффективный и безопасный способ коррекции зрения без хирургического вмешательства. Новые капли, созданные на основе пилокарпина и диклофенака, показали убедительные результаты: уже через час после первого пр ...>>

Случайная новость из Архива Нейронный шум помогает учиться 30.03.2015 Двадцать лет назад нейробиологи из Стэнфорда обнаружили у некоторых нейронов мозга странную шумовую активность: они реагировали на такие стимулы, которые, казалось, не имели к ним никакого отношения. И такая активность возникала именно тогда, когда мозг принимал какое-то решение. Сам же эксперимент состоял в следующем: подопытные животные должны были определить, как движутся точки на экране, справа налево или слева направо; в случае правильного ответа выдавалась награда. С помощью такой модели можно изучать, какие процессы в мозге сопровождают формирование категорий. Категоризация объектов и явлений - одна из самых общих особенностей психики, лежащая в основе обучения, и действительно было бы интересно узнать, что в этот момент происходит в мозге. В данном случае, как легко понять, нужно было выделить два класса объектов: те, что движутся в одну сторону, и те, что движутся в противоположную сторону. В результате удалось обнаружить группу нейронов, реагирующих на движение, причем среди них были такие, которые становились особенно активны именно в момент принятия решения. Однако активность их выглядела так, как если бы одни клетки в ответ на точку кричали "справа налево!", а другие в ответ на ту же самую точку - "слева направо!", вне зависимости от того, куда на самом деле точка движется. Уровень шума снижался с помощью вознаграждения за правильный ответ - оно настраивало нейроны, делая их более разборчивыми и менее шумными, так что они начинали реагировать большей частью только на точки какой-то одной, "своей", категории. Причем особенно странно было то, что нейронный шум происходил вовсе не в тех участках коры, которые обычно связаны с принятием решения. Зачем шумят нейроны в "непрофильном" отделе мозга, удалось отчасти выяснить только сейчас, с помощью компьютерной модели, разработанной Татьяной Энгил (Tatiana Engel) и ее коллегами; результаты их работы опубликованы в Nature Communications. Модель имитировала работу нейронных цепей, связывающих сенсорные области мозга с категоризирующими. Виртуальные нейроны "наблюдали" точки, которые двигались в разные стороны и которые нужно было распределить по таким же двум классам, "правому" и "левому" - как и в исходном эксперименте с животными. Смоделированную нейронную цепь, в отличие от настоящей, можно лишить способности шуметь, что исследователи и сделали. Но оказалось, что без нейронного шума, сопровождающего выбор, невозможно формирование категорий. Иными словами, для того, чтобы в уме сформировался класс точек, движущихся справа налево, мозг должен делать выбор в "шумных" условиях, когда часть нейронов одновременно будут "агитировать" за неправильный ответ. Если отвлечься от точек и подобрать более жизненный пример, то представим, что вы каждое утро выбираете между чашкой кофе и чашкой чая. Вы делаете выбор каждый день в течение недели, двух недель, месяца, полугода, и в конце концов приходите к мысли, что утренняя чашка кофе - именно то, что надо. Но если вдруг случится так, что ваш мозг будет делать выбор без всякого шума, то у вас просто не сформируется связи между утренними часами и кофе, само понятие утреннего кофе будет отсутствовать. Конечно, здесь есть большое искушение интерпретировать нейронный шум как "сомнение", или как "необходимость рассматривать все варианты решения из возможных". Впрочем, такие формулировки относятся, скорее, к области философии, которую мы пока вряд ли можем соотнести с конкретными нейрофизиологическими феноменами. Однако вполне может быть, что новые данные в будущем позволят создать какие-нибудь аппаратные методы, улучшающие когнитивные способности - через управление нейронным шумом. Но пока что предстоит выяснить, откуда он, собственно, берется: то ли это сенсорные отделы его генерируют, то ли его производят другие области мозга, которые непосредственно связаны с принятием решений, или же здесь задействованы и сенсорный, и когнитивный отделы вместе.

Другие интересные новости:

▪ Автомобильные технологии будущего от Hyundai

▪ Защищенный ноутбук Gigabyte U4

▪ Счастье от альтруизма недолговечно

▪ CPU-кулер ID-Cooling SE-50

▪ Сажа на крыше мира

Лента новостей науки и техники, новинок электроники

Интересные материалы Бесплатной технической библиотеки:

▪ раздел сайта Сборка кубика Рубика. Подборка статей

▪ статья Переделка стиральной машины под слабый напор воды. Советы домашнему мастеру

▪ статья Когда появились первые автоматы, в которые нужно было бросать монеты? Подробный ответ

▪ статья Уборщик производственных помещений. Должностная инструкция

▪ статья Принципы экономии электроэнергии. Энциклопедия радиоэлектроники и электротехники

▪ статья Торфяные электроустановки. Подстанции. Энциклопедия радиоэлектроники и электротехники

Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2025