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. Список списков.

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

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

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

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

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

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

▪ Поведение потребителей. Шпаргалка

▪ Русская литература XX века в кратком изложении. Шпаргалка

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

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

<< Назад

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

Большой адронный коллайдер прекращает работу 16.01.2026

Физика элементарных частиц - одна из самых передовых областей науки, где каждый эксперимент может изменить наше понимание мироздания. Центральным инструментом этих исследований является Большой адронный коллайдер (LHC), уникальный ускоритель частиц, позволяющий изучать самые фундаментальные законы природы. Недавно стало известно, что LHC временно прекращает свою работу для масштабной модернизации, которая подготовит его к новому этапу экспериментов с гораздо большей производительностью. Коллайдер, расположенный в подземном тоннеле вдоль швейцарско-французской границы, создает столкновения частиц на невероятно высоких энергиях. Именно здесь в 2012 году ученые открыли бозон Хиггса - ключевую частицу, объясняющую, почему другие элементарные частицы имеют массу. Это открытие стало одним из самых значимых событий современной физики и подтвердило предсказания Стандартной модели. Причиной временной остановки LHC стало развертывание проекта High-Luminosity LHC (HL-LHC). Модернизация позв ...>>

Робот-бармен AI Barmen 16.01.2026

Американские инженеры создали AI Barmen - робота-бармена, способного не только готовить коктейли, но и запоминать предпочтения гостей. AI Barmen представляет собой автономную систему, которую можно устанавливать практически в любых местах - от баров и ресторанов до гостиниц, аэропортов и корпоративных мероприятий. Робот сочетает механический манипулятор с интеллектуальной программой, которая подбирает напитки на основе истории заказов конкретного пользователя. Гости могут оставаться анонимными или разрешить системе запоминать их вкусы, что позволяет получать одинаково качественный персонализированный коктейль в любой точке, где установлен AI Barmen. Робот готовит широкий спектр коктейлей с высокой точностью, контролирует запасы ингредиентов и автоматически ведет учет, что снижает затраты и минимизирует ошибки. Для работы устройства достаточно стандартной розетки, подключение к воде не требуется, что делает его мобильным и удобным для эксплуатации в самых разных условиях. Систе ...>>

Стерильного нейтрино не существует 15.01.2026

В физике элементарных частиц поиск новых, пока не обнаруженных объектов играет ключевую роль в понимании устройства Вселенной. Иногда такие поиски приводят к громким открытиям, а иногда - к не менее важным отрицательным результатам, которые позволяют отбросить неверные направления. Именно к таким случаям относится недавний вывод ученых о судьбе стерильного нейтрино - одной из самых интригующих гипотетических частиц последних десятилетий. Исследователи из американской лаборатории Fermilab официально сообщили, что им не удалось найти доказательства существования стерильного нейтрино. К такому выводу пришла команда эксперимента MicroBooNE после многолетнего анализа столкновений нейтрино, которые ранее рассматривались как возможный намек на существование четвертого типа этих частиц. Предполагалось, что стерильное нейтрино взаимодействует с материей исключительно через гравитацию, что делало его крайне трудным объектом для обнаружения. В рамках современной физики нейтрино известны в т ...>>

Случайная новость из Архива ИИ для быстрого поиска лекарств 14.07.2022 Исследователи Массачусетского технологического института разработали модель глубокого обучения EquiBind, которая в 1200 раз быстрее аналогов связывает молекулы с белками при создании лекарств. Перед началом разработки лекарства исследователи должны сперва найти молекулы, способные "состыковываться" с определенными белками-мишенями. Однако этот процесс требует значительных финансовых и вычислительных средств. Более того, на разработку и тестирование нового лекарства уходят десятки лет, а 90% открытий терпят неудачу, заявили ученые. По словам ведущего автора исследования Ханнеса Штарка, существующие методы связывания лиганда с белком напоминают "попытки вставить ключ в замок с большим количеством замочных скважин". "Типичные модели отнимают много времени и оценивают каждое соответствие, прежде чем выбрать лучший вариант. Напротив, EquiBind напрямую предсказывает точное расположение ключа за один шаг без предварительного знания целевого кармана белка, что известно как "слепая стыковка". По словам исследователей, модель имеет встроенные геометрические рассуждения, которые помогают ей изучать основную физику молекул и делать более точные прогнозы при столкновении с новыми, неизвестными данными. Директор по данным биотехнической компании Relay Therapeutics Пэт Уолтерс предложил ученым испытать систему на существующем лекарстве и белке, используемых в лечении рака легких, лейкемии и опухолях желудочно-кишечного тракта. По его словам, алгоритм успешно связал лиганды с белками, чего не удалось сделать традиционными методами. "EquiBind предлагает уникальное решение проблемы стыковки, которое включает в себя как предсказание позы, так и идентификацию места привязки", - говорит Уолтерс. Исследователи планируют представить алгоритм на Международной конференции по машинному обучению. Штарк заявил, что команда намерена собрать больше отзывов о системе от специалистов в отрасли, чтобы улучшить ее.

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

▪ DC/DC преобразователь TPS6284x от Texas Instruments

▪ Финская энергия ветра превзошла энергию воды

▪ Вода из ветра

▪ За стеной видны микрообъекты

▪ Старые деревья более устойчивы к засухе

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

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

▪ раздел сайта Электротехнические материалы. Подборка статей

▪ статья Больше поэтов, хороших и разных. Крылатое выражение

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

▪ статья Кровотечение после удаления зуба. Медицинская помощь

▪ статья Переносный аппарат для точечной электросварки. Энциклопедия радиоэлектроники и электротехники

▪ статья Загадки про цветы и растения

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

www.diagram.com.ua
2000-2026