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

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

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

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

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

▪ Лор-заболевания. Конспект лекций

▪ Реклама. Шпаргалка

▪ История государства и права зарубежных стран. Шпаргалка

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

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

<< Назад

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

Хорошо управляемые луга могут компенсировать выбросы от скота 15.02.2026

Животноводство, особенно разведение крупного рогатого скота, часто обвиняют в значительном вкладе в глобальное потепление из-за мощного парникового газа - метана, который выделяется при пищеварении у жвачных животных. Это вызывает острые политические споры и призывы к сокращению потребления мяса. Однако ученые напоминают, что полная картина климатического воздействия отрасли не ограничивается только выбросами от животных: огромную роль играет окружающая экосистема - пастбища, почва и растительность, которые способны активно поглощать углекислый газ из атмосферы. Исследователи из Университета Небраски-Линкольна решили глубже изучить этот баланс. Группа под руководством профессора Галена Эриксона сосредоточилась на том, как правильно организованные пастбища накапливают углерод в растениях и грунте благодаря естественным процессам, стимулируемым выпасом скота. Ученые подчеркивают, что при достаточном уровне осадков и грамотном управлении такие луга превращаются в мощные природные погло ...>>

NASA тестирует инновационную технологию крыла 15.02.2026

Коммерческая авиация ежегодно расходует колоссальные объемы керосина, что сказывается не только на бюджете авиакомпаний, но и на состоянии окружающей среды. В 2024 году глобальные затраты на авиационное топливо достигли 291 миллиарда долларов, и эта сумма продолжает расти. Чтобы справиться с этими вызовами, NASA активно работает над технологиями, способными заметно повысить аэродинамическую эффективность самолетов. Одним из самых перспективных направлений стало создание специальной конструкции крыла, которая максимизирует естественный ламинарный поток воздуха и минимизирует сопротивление. В январе 2026 года специалисты NASA Armstrong Flight Research Center успешно провели важный этап наземных испытаний концепции Crossflow Attenuated Natural Laminar Flow (CATNLF). Для эксперимента под фюзеляж исследовательского самолета F-15B закрепили вертикально ориентированную масштабную модель высотой около 0,9 м (3 фута), напоминающую узкий киль. Такая компоновка позволила подвергнуть прототип р ...>>

Забота о внуках очень полезна для здоровья мозга 14.02.2026

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

Случайная новость из Архива Yongnuo YN455 - беззеркальная камера на Android 16.07.2021 Китайская компания Yongnuo представила новую беззеркальную камеру YN455, главной отличительной особенностью которой стало использование операционной системы Android. Новинка получила 20-мегапиксельный сенсор Micro Four Thirds и поддержку сменных объективов. Камера умеет снимать видеоролики разрешением 4К 3840 х 2160 пикселей на скорости 30 кадров в секунду. Новинка построена на базе не названного пока восьмиядерного процессора Snapdragon от Qualcomm, работающего на тактовой частоте до 2,2 ГГц. Предусмотрено 6 Гбайт оперативной памяти и постоянный накопитель объемом 64 Гбайт, с возможностью расширения посредством карты формата microSD емкостью до 256 Гбайт. Для управления камерой и просмотра сделанных кадров предусмотрен 5-дюймовый наклонный сенсорный экран. Аккумулятор съемный, емкостью 4400 мАч. Есть два порта USB Type-C, 3,5-миллиметровый комбинированный аудиоразъем, Wi-Fi, Bluetooth и GPS, а также 4G-модем.

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

▪ Крошечные устройства доставят лекарство в организм человека

▪ Новый антибактериальный композит получен с помощью плазмы

▪ Генетика одиночества

▪ Китайский Питон ремонтирует дороги

▪ В Android Market уже 38 тыс. приложений

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

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

▪ раздел сайта Опыты по физике. Подборка статей

▪ статья Есть у революции начало - нет у революции конца. Крылатое выражение

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

▪ статья Фен для сварки. Домашняя мастерская

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

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

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

www.diagram.com.ua
2000-2026