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

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

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

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

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

▪ Международное частное право. Конспект лекций

▪ Бухгалтерский учет. Конспект лекций

▪ Информационное право. Шпаргалка

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

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

<< Назад

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

Тающие айсберги создают новые оазисы жизни на дне океана 30.06.2026

Глобальное потепление активно меняет облик нашей планеты, и одним из наиболее заметных его проявлений становится ускоренное таяние ледников в полярных регионах. Этот процесс не только приводит к подъему уровня Мирового океана, но и вызывает цепную реакцию в морских экосистемах, порой создавая неожиданные и парадоксальные последствия. Массовое высвобождение айсбергов из Гренландии - яркий пример того, как климатические изменения перестраивают жизнь в самых глубоких и удаленных уголках океана. Из-за повышения температуры количество айсбергов, откалывающихся от гренландских ледников, стремительно растет. Ученые проанализировали данные за последние 40 лет и установили, что с 2000 года поток ледяных глыб через пролив Фрама увеличился в четыре раза. Об этом сообщает Futurism со ссылкой на исследование специалистов из Технического университета Дании. Такое беспрецедентное нашествие айсбергов представляет серьезную опасность для международного судоходства. Одновременно оно радикально тра ...>>

Робот-тьютор Optio, помошник школьника 30.06.2026

Икусственный интеллект и робототехника все активнее помогают учителям и ученикам, делая обучение более персонализированным и увлекательным. Гуманоидные роботы, способные взаимодействовать с людьми естественным образом, открывают новые возможности для школ, особенно в условиях нехватки педагогических кадров и растущего интереса к технологиям. Одна из таких инновационных инициатив стартовала в американском штате Нью-Йорк. Компания Realbotix запустила своего помощника учителя на базе искусственного интеллекта под названием Optio в Центральном школьном округе Саламанки. Робот выступает в роли тьютора, предлагая персонализированное репетиторство, многоязычную помощь с домашними заданиями и круглосуточную академическую поддержку. По данным Interesting Engineering, проект направлен на повышение вовлеченности учащихся и внедрение передовых технологий в учебный процесс. В рамках пилотной программы школы округа планируют интегрировать человекоподобных роботов в классы. Изначально Optio буд ...>>

Биопрепараты повышают питательную ценность органической гречихи 29.06.2026

В органическом земледелии особое внимание уделяется не только урожайности, но и качественному составу продукции. Потребители все чаще выбирают продукты с высоким содержанием полезных веществ и без следов химических веществ. Исследования показывают, что применение биологических препаратов может существенно улучшить минеральный состав зерновых культур, делая их более ценными с точки зрения питания. В результате полевых экспериментов, проведенных в 2023-2025 годах, ученые установили, что использование биопрепаратов способствует активному накоплению макроэлементов, в частности фосфора и калия, в зерне органической гречихи. Об этом сообщила Леся Крупак из Белоцерковского национального аграрного университета в своей работе "Экологичность и производительность". Наиболее заметный эффект наблюдался при применении гумата калия. В этом случае содержание калия в зерне увеличивалось на 19-21 процент по сравнению с контрольными участками. Такой результат свидетельствует об улучшении работы тра ...>>

Случайная новость из Архива IP-камера D-Link DCS-935L 24.05.2015 Компания D-Link объявила о начале поставок DCS-935L - своей первой IP-камеры потребительского сегмента, поддерживающей Wi-Fi 802.11ac. По мнению производителя, дома или в небольшом офисе будут востребованы такие особенности камеры, как функции обнаружения звуков и движения, возможность работы в дневном и ночном режимах. Подключение по 802.11ac в диапазоне 5 ГГц обеспечивает лучшее качество связи и большую пропускную способность для передачи видео. Конечно, камера может работать и в диапазоне 2,4 ГГц. Угол поля зрения DSC-935L по горизонтали равен 78°. Камера поддерживает разрешение до 720p при кадровой частоте 30 к/с. Для первоначальной настройки используется мобильное приложение mydlink Home, доступное в версиях для iOS и Android. Питание камеры подается на разъем microUSB. Соответствующий сетевой адаптер включен в комплект. Цена DCS-935L - $120.

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

▪ Солнечные панели LG NeON R и NeON R Prime

▪ Флуоресцентные датчики укажут на органические загрязнители воды

▪ Раскрыт секрет походки динозавров

▪ Новая Зеландия запустила первую космическую ракету

▪ Долгоиграющая беспроводная колонка XBOOM Go Jellybean

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

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

▪ раздел сайта Инструкции по эксплуатации. Подборка статей

▪ статья Эрнст Геккель. Знаменитые афоризмы

▪ статья Зачем англичане построили в 19 веке живую изгородь через всю Индию? Подробный ответ

▪ статья Растения пустыни. Советы туристу

▪ статья Средства для маникюра. Простые рецепты и советы

▪ статья Воздух толкается. Физический эксперимент

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

www.diagram.com.ua
2000-2026