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

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

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

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

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

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

▪ Нотариат. Шпаргалка

▪ Стратегический менеджмент. Шпаргалка

▪ Хирургические болезни. Шпаргалка

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

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

<< Назад

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

Большой адронный коллайдер прекращает работу 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 после многолетнего анализа столкновений нейтрино, которые ранее рассматривались как возможный намек на существование четвертого типа этих частиц. Предполагалось, что стерильное нейтрино взаимодействует с материей исключительно через гравитацию, что делало его крайне трудным объектом для обнаружения. В рамках современной физики нейтрино известны в т ...>>

Случайная новость из Архива Наушники Sony XB900N 27.05.2019 Компания Sony представила новые беспроводные наушники накладного типа - XB900N. Модель получила 40-миллиметровые излучатели с неодимовыми магнитами. Предусмотрена поддержка технологии Extra Bass, позволяющая реализовать насыщенные низкие частоты. Есть и встроенный микрофон, позволяющий использовать наушники в качестве гарнитуры и обращаться к интеллектуальному голосовому помощнику на синхронизированном смартфоне. Для связи с последним имеется модуль Bluetooth 4.2 и NFC-чип, обеспечивающий быстрое подключение к источнику сигнала. Также сообщается о наличии системы шумоподавления. Беспроводные наушники отличаются достойными показателями автономности. Без использования системы шумоподавления они могут прожить на одном заряде до 35 часов, а с активацией "шумодава" - до 30 часов. Правда, заряжаются Sony XB900N весьма неспешно - порядка семи часов. Цена новинки составляет 250 долларов США.

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

▪ LG выпустит сверхчеткий 84-дюймовый 3D-телевизор

▪ Вертолет с мускульным приводом

▪ Обнаружена самая глубоководная рыба в мире

▪ Белый-белый жук

▪ Сети из нанопроволоки учатся и запоминают как человеческий мозг

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

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

▪ раздел сайта Звонки и аудио-имитаторы. Подборка статей

▪ статья История политических и правовых учений. Шпаргалка

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

▪ статья Врач-детский хирург. Должностная инструкция

▪ статья Сигнализатор ручного тормоза автомобиля. Энциклопедия радиоэлектроники и электротехники

▪ статья Резисторы прецизионные высокостабильные PANASONIC. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2026