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

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

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

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

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

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

контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом.

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

Существуют различные способы представления графов.

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

Это прямоугольная матрица размерности n ч m, где n - количество вершин, а m - количество ребер.

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

Это квадратная матрица размерности n ч n, где n - количество вершин.

3. Список смежности (инцидентности). Представляет собой структуру данных, которая

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

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

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

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

<< Назад: Примеры реализации операций

>> Вперед: Различные представления графа

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

▪ Общая психология. Шпаргалка

▪ Реклама и рекламная деятельность. Конспект лекций

▪ История психологии. Шпаргалка

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

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

<< Назад

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

Лабораторная модель прогнозирования землетрясений 30.11.2025

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

Музыка как естественный анальгетик 30.11.2025

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

Алкоголь может привести к слобоумию 29.11.2025

Проблема влияния алкоголя на стареющий мозг давно вызывает интерес как у врачей, так и у исследователей когнитивного старения. В последние годы стало очевидно, что границы "безопасного" употребления спиртного размываются, и новое крупное исследование, проведенное международной группой ученых, вновь указывает на это. Работы Оксфордского университета, выполненные совместно с исследователями из Йельского и Кембриджского университетов, показывают: даже небольшие дозы алкоголя способны ускорять когнитивный спад. Команда проанализировала данные более чем 500 тысяч участников из британского биобанка и американской Программы миллионов ветеранов. Дополнительно был выполнен метаанализ сорока пяти исследований, в общей сложности включавших сведения о 2,4 миллиона человек. Такой масштаб позволил оценить не только прямую связь между употреблением спиртного и развитием деменции, но и влияние генетической предрасположенности. Один из наиболее тревожных результатов касается людей с повышенным ге ...>>

Случайная новость из Архива Болезни выходного дня 04.12.2004 Некоторые из нас болеют только во время отпуска или в выходные, но ни единого рабочего дня по болезни не пропускают. Голландский психолог Ад Вингерхутс заинтересовался этим феноменом. Опросив 1893 человека, он пришел к выводу, что свыше трех процентов голландцев страдают так называемым "синдромом свободного времени": они болеют преимущественно в выходные или во время отпуска. Среди наиболее частых недомоганий - постоянная усталость, мышечные боли, грипп и простуда. Причем простуда появляется преимущественно в первую неделю отпуска. По мнению опрошенных психологом страдальцев, причина заболеваний - трудности переключения организма с рабочего ритма на отдых. Видимо, влияет и стресс, наступающий при подготовке к отпуску, когда надо срочно уладить и рабочие, и домашние дела. Многие из болеющих в свободное время относятся к своей работе очень ответственно и не умеют расслабляться, хотя проводят на работе не больше времени, чем не затронутые этим синдромом. Как правило, они не чаще других занимают особо ответственные должности. Такие люди просто по-иному относятся к своим служебным обязанностям. Однозначного научного объяснения синдрому свободного времени пока нет. Возможно, это реакция иммунной системы на стресс при переключении с работы на отдых.

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

▪ Гены против гравитации

▪ Мотороллер на водороде

▪ Жидкокристаллическая структура человеческой РНК

▪ SSD TeamGroup M.2 с жидкостной системой охлаждения

▪ Антикризисные LED драйверы FDL-65 от от Mean Well

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

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

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

▪ статья Соответствие моделей и шасси видеокамер GRUNDIG. Справочник

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

▪ статья Алтей аптечный. Легенды, выращивание, способы применения

▪ статья Защита ИП с помощью аналогового перемножителя КР525ПС2. Энциклопедия радиоэлектроники и электротехники

▪ статья Бестрансформаторный преобразователь напряжения, 12/22 вольта 30 миллиампер. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2025