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

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

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

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

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

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

▪ Аграрное право. Шпаргалка

▪ Статистика. Шпаргалка

▪ Хирургические болезни. Конспект лекций

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

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

<< Назад

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

Питомцы как стимулятор разума 06.10.2025

Помимо эмоциональной поддержки, домашние питомцы могут оказывать заметное воздействие на когнитивные процессы, особенно у пожилых людей. Новое масштабное исследование показало, что общение с кошками и собаками не просто улучшает настроение - оно действительно способствует замедлению возрастного снижения умственных способностей. Работа проводилась в рамках проекта Survey of Health, Ageing and Retirement in Europe (SHARE), охватывающего период с 2004 по 2022 год. В исследовании приняли участие тысячи европейцев старше 50 лет. Анализ показал, что владельцы домашних животных демонстрируют более устойчивые когнитивные функции по сравнению с теми, кто не держит питомцев. Особенно выражен эффект оказался у владельцев кошек и собак. Согласно данным ученых, владельцы собак дольше сохраняют хорошую память, в то время как хозяева кошек медленнее теряют способность к быстрому речевому взаимодействию. Исследователи связывают это с тем, что ежедневное взаимодействие с животными требует внимани ...>>

Мини-ПК ExpertCenter PN54-S1 06.10.2025

Компания ASUSTeK Computer презентовала новый мини-компьютер ASUS ExpertCenter PN54-S1. Устройство ориентировано на пользователей, которым важно сочетание производительности, энергоэффективности и универсальности - от офисных задач до мультимедийных проектов. В основе ExpertCenter PN54-S1 лежит современная аппаратная платформа AMD Hawk Point, использующая архитектуру Zen 4. Это поколение чипов отличается улучшенным управлением энергопотреблением и повышенной вычислительной мощностью. Новинка доступна в конфигурациях с процессорами Ryzen 7260, Ryzen 5220 и Ryzen 5210, представленных AMD в начале 2025 года. Таким образом, устройство охватывает широкий диапазон задач - от базовых офисных до ресурсоемких вычислений. Корпус мини-ПК выполнен из прочного алюминия и имеет размеры 130&#215;130&#215;34 мм, что делает его практически незаметным на рабочем столе или за монитором. Несмотря на компактность, внутренняя компоновка позволяет установить два модуля оперативной памяти SO-DIMM ...>>

Глазные капли, возвращающие молодость зрению 05.10.2025

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

Случайная новость из Архива Ноутбук Lenovo ThinkBook X AI 2024 26.03.2024 Компания Lenovo представила новый ноутбук ThinkBook X AI 2024, который стал первым в мире ноутбуком, изготовленным из нержавеющего магниевого сплава. Ноутбук Lenovo ThinkBook X AI 2024 представляет собой передовое техническое решение, объединяющее в себе инновационные материалы, высокую производительность и широкий функционал. Это устройство обещает стать надежным партнером для профессионалов и энтузиастов, предпочитающих передовые технологии. Lenovo ThinkBook X AI 2024 оснащен 13,5-дюймовым дисплеем с разрешением 2,8K, частотой обновления 120 Гц и соотношением сторон 3:2. В его основе лежит процессор Intel Core Ultra 9, 32 ГБ оперативной памяти LPDDR5X и до 2 ТБ флэш-памяти. Вес устройства составляет всего 1 кг, а толщина корпуса - 12,9 мм. Устройство питается аккумулятором емкостью 74 Втч, обеспечивающим до 21 часа непрерывного воспроизведения видео. Ноутбук оборудован тремя интерфейсами Thunderbolt 4, аудиоразъемом 3,5 мм и четырьмя динамиками от Harman Kardon. Он работает под управлением операционной системы Windows 11 и оснащен Bluetooth 5.2, WiFi 6E, сканером отпечатков пальцев в кнопке включения, веб-камерой FHD, ИК-датчиком, замком Kensington и шторкой конфиденциальности для камеры.

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

▪ Генномодифицированные личинки заживляют раны

▪ Зеркальная камера Nikon D5000

▪ Страсти вокруг видео-форматов

▪ Сверхмассивная звезда

▪ Цельностеклянные металлинзы для телескопов

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

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

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

▪ статья Рыцарь на час. Крылатое выражение

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

▪ статья Аскания-Нова. Чудо природы

▪ статья Особенности монтажа электропроводок. Общие положения. Энциклопедия радиоэлектроники и электротехники

▪ статья Зарядная приставка для мультиметра. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2025