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

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

Случайная новость из Архива Биометрические линзы сделают зрение в три раза острее 30.05.2015 Стандартным хорошим зрением в области офтальмологии является так называемая "единичка" (1,0). Но технологии могут перевернуть представление о совершенном зрении. Линза Ocumetrics Bionic Lens выводит коррекцию зрения на совершенно новый уровень и, по мнению канадского оптометриста доктора Гарта Вебба (Garth Webb), является будущим отрасли. Благодаря Ocumetrics Bionic Lens зрение человека будет обладать в три раза более высокой остротой по сравнению с нормальной "единичкой". В идеальном варианте эта линза будет имплантироваться в глаз пациента возрастом от 25 лет, когда зрительная система полностью сформирована. В настоящее время проходят клинические исследования новинки. Как отметил офтальмолог доктор Винсент ДеЛуиз (Vincent DeLuise), Ocumetrics Bionic Lens обеспечит прекрасную остроту зрения на средних дистанциях, вдали и вблизи. В случае успешного проведения всех исследований и завершения разработки серийного производственного процесса новинка может стать доступной уже в ближайшие два года.

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

▪ Ручка Nuwa Pen оцифрует рукописный текст в реальном времени

▪ Из ревеня - не только компот

▪ Духи, заменяющие кофе

▪ Растворимый пластик из манго и водорослей

▪ Amazon Go: супермаркет без кассиров и очередей

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

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

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

▪ статья Авогадро Амедео. Биография ученого

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

▪ статья Растяжения и разрывы связок. Медицинская помощь

▪ статья Искусственный рог. Простые рецепты и советы

▪ статья УКВ ЧМ радиостанция. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2026