ЛЕКЦИЯ № 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;

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

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

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

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

▪ Антикризисное управление. Конспект лекций

▪ Социальная психология. Конспект лекций

▪ История мировой и отечественной культуры. Шпаргалка

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

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

<< Назад

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

Донорское сердце способно быстро перенимать биологический возраст реципиента 12.10.2026

Возраст органов определяется не только количеством прожитых лет. На молекулярном уровне ткани могут стареть с разной скоростью, а после пересадки, как показывают новые эксперименты, их биологические характеристики способны заметно меняться под воздействием организма, в который они попадают. Исследователи из Бостона обнаружили, что молодые донорские сердца после трансплантации довольно быстро приобретают признаки биологического возраста реципиента, тогда как более старые органы могут, напротив, демонстрировать признаки омоложения. Чтобы оценить эти изменения, ученые применили три так называемых "часа старения" - молекулярных инструмента, позволяющих приблизительно определять биологический возраст клеток и тканей. В отличие от обычного календарного возраста, такие показатели отражают состояние организма на уровне определенных молекулярных изменений. Именно их анализ позволил специалистам проследить, как меняются пересаженные сердца спустя несколько месяцев после операции. Основные ...>>

Samsung Galaxy Buds On: клипсы с искусственным интеллектом вместо внутриканальных наушников 12.10.2026

Беспроводные наушники превратились в одно из самых привычных персональных электронных устройств, однако их конструкция по-прежнему во многом определяется необходимостью размещать излучатель внутри или непосредственно у слухового канала. Компания Samsung решила попробовать другой подход. Представленная модель Galaxy Buds On получила формат наушников-клипсов, которые закрепляются непосредственно на ухе и оставляют слуховой канал открытым. Samsung позиционирует новинку как устройство для продолжительного ношения, тренировок и прогулок, а также для ситуаций, когда пользователю важно одновременно слушать музыку и не терять связь с окружающей обстановкой. В отличие от традиционных внутриканальных моделей, Galaxy Buds On практически не изолируют человека от внешнего мира. При этом речь идет не об экспериментальном прототипе или утечке: официальная информация об устройстве уже опубликована в Samsung Newsroom. Открытая конструкция имеет и очевидный недостаток - добиться такой же глубины н ...>>

Ферроэлектрики научились выдерживать более 10 миллиардов циклов перезаписи 11.10.2026

Энергонезависимая память должна не только быстро записывать и сохранять информацию без постоянного питания, но и выдерживать огромное количество циклов перезаписи. Одним из перспективных вариантов такой технологии считаются ферроэлектрические материалы, однако их практическое применение долгое время ограничивалось сравнительно быстрым разрушением. Исследователям удалось установить механизм этого процесса на атомном уровне и предложить способ, который значительно увеличивает срок службы таких материалов. Работу выполнила группа ученых из Университета электронной науки и техники Сианя (Xidian University) совместно с коллегами из Гонконгского университета и Фуданского университета. Особый интерес специалистов вызвали ферроэлектрики со структурой вюрцита, в частности нитрид алюминия-скандия (AlScN). Эти материалы способны сохранять информацию благодаря изменению направления электрической поляризации на атомном уровне и хорошо совместимы с современными технологиями производства микросхем ...>>

Случайная новость из Архива Дистанционное управление мягкими роботами 27.04.2020 Найден способ дистанционного управления пластичными роботами. Вместо громоздких приводов, кабелей и механических конструкций движение гибких частей машин будет регулироваться переменным магнитным полем. Способ позволил достичь большей функциональности, чем классические методы управления роботами. Роботы из мягких материалов, таких как резина и полимеры, незаменимы при поисково-спасательных работах, когда необходимо протискиваться через узкие отверстия и совершать при этом сложные манипуляции. Широкий функционал требуется и медицинским устройствам, которые перемещаются внутри человеческого тела. Управлять "гибкими" роботами из мягких материалов до недавнего времени могли лишь с помощью приводных механизмов, которые нередко были больше самих роботов. Исследователи из Висконсинского университета придумали способ дистанционного управления "мягкими" роботами. Внутри пластичного материала равномерно распределили мелкие намагниченные частицы. Затем на материал действовали магнитным полем различной интенсивности, получая требуемый отклик от частей материала. Новый подход к управлению пластичными материалами с помощью магнитного поля раскрыл даже больший функционал, чем механические способы регулирования движения.

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

▪ Влагозащищенный электросамокат Predator Extreme PES017

▪ Тепловой след откроет пин-код смарфона

▪ TPS62510 - 1,5 А понижающий преобразователь для портативных устройств

▪ Метавселенная может оказаться хуже социальных сетей

▪ Экономичный очиститель воды на солнечной энергии

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

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

▪ раздел сайта Телефония. Подборка статей

▪ статья Раздавите гадину! Крылатое выражение

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

▪ статья Машинист баровой машины. Типовая инструкция по охране труда

▪ статья Антенна GROUND PLANE на 7 МГц. Энциклопедия радиоэлектроники и электротехники

▪ статья Радиоприемник на микросхеме К174ХА10. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2026