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

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

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

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

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

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

▪ Этика. Шпаргалка

▪ Страховое право. Шпаргалка

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

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

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

<< Назад

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

Дети, растущие рядом с природой, обретают крепкие кости 02.03.2026

Влияние окружающей среды на здоровье человека становится все более очевидным, особенно в детском возрасте. Новое исследование, опубликованное в журнале JAMA Network Open, показывает, что близость к природе напрямую связана с крепостью костей у детей. Ученые установили, что у детей, чьи дома окружены природными территориями в радиусе 1000 метров на 25% больше обычного, риск развития крайне низкой плотности костей снижается на 65%. Для проведения исследования были проанализированы данные более 300 детей, проживающих в городских, пригородных и сельских районах Фландрии в Бельгии. Плотность костной ткани у детей в возрасте от четырех до шести лет оценивалась с помощью ультразвуковых методов. Такой подход позволил безопасно и точно измерить состояние костей на ранних этапах формирования скелета. При анализе учитывались ключевые факторы, влияющие на рост и развитие детей: возраст, вес, рост, этническая принадлежность и уровень образования матери. На основании этих параметров исследоват ...>>

Самовосстанавливающаяся инфраструктура будущего 02.03.2026

Современные мосты и бетонные конструкции по всему миру сталкиваются с проблемой устаревания и износа. Многие сооружения, построенные до 1980-х годов, постепенно теряют свою несущую способность, что требует дорогого ремонта или полной замены. Недавние разработки ученых из Швейцарских федеральных лабораторий материаловедения и технологий (Empa) предлагают инновационное решение - систему укрепления бетонных конструкций с помощью "умной стали", способной самостоятельно устранять трещины и повреждения. В основе новой технологии лежит арматура из сплава на основе железа с эффектом памяти формы (Fe-SMA). Этот материал обладает уникальным свойством: при нагревании до 190-200 °C стержни стремятся вернуться к своей первоначальной конфигурации. В бетонной конструкции это создает внутреннее напряжение, которое затягивает трещины и выравнивает деформированные элементы, существенно повышая прочность и долговечность сооружений. Актуальность разработки объясняется критическим состоянием инфрастр ...>>

Поцелуи полезны для здоровья 01.03.2026

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

Случайная новость из Архива Лазерная подзарядка дронов в полете 25.12.2025 Даже самые совершенные дроны вынуждены возвращаться на базу для подзарядки, что сокращает время их работы и ограничивает возможности применения. Именно эту фундаментальную проблему пытаются решить американские инженеры, предложив технологию лазерной подзарядки беспилотников прямо в воздухе. Компания PowerLight Technologies объявила о завершении разработки и успешных испытаний беспроводной системы энергоснабжения, основанной на использовании лазерного излучения. Проект реализуется при поддержке Центрального командования США (CENTCOM) в рамках программы PTROL-UAS, цель которой - радикально увеличить продолжительность полета военных дронов без необходимости посадки. В основе технологии лежит связка из автономного высокомощного лазерного передатчика и компактного бортового приемника, которые вместе формируют своеобразную "воздушную энергетическую линию". Система способна передавать несколько киловатт энергии беспилотникам, находящимся на расстоянии нескольких миль и на высоте до 1,5 километра. Во время испытаний была подтверждена возможность точного наведения лазерного луча на движущуюся цель и стабильной передачи энергии в режиме реального времени. Особое внимание разработчики уделили мобильности и безопасности наземного сегмента. Лазерный передатчик рассчитан на использование в полевых условиях и оснащен системой точного управления лучом, работающей совместно с программным обеспечением автоматического отслеживания дружественных летательных аппаратов. Это позволяет минимизировать риски и обеспечить контролируемую передачу энергии в общем воздушном пространстве. Для самих дронов PowerLight создала легкий приемный модуль массой около 2,7 килограмма. Он преобразует невидимое лазерное излучение в электрическую энергию, которая используется для подзарядки аккумуляторов на борту. Встроенный блок управления собирает телеметрические данные и передает их на наземную станцию, одновременно формируя технологическую основу для будущего использования оптических каналов связи между дроном и оператором. Система включает несколько уровней автоматического контроля и мониторинга, что позволяет ей безопасно функционировать рядом с другими воздушными объектами. Такой подход делает лазерную подзарядку не экспериментальной демонстрацией, а потенциально масштабируемым решением для реальных условий эксплуатации. Для практической интеграции технологии PowerLight сотрудничает с компанией Kraus Hamdani Aerospace. Лазерная система энергоснабжения встраивается в беспилотник K1000ULE - аппарат сверхпродолжительного действия, разработанный для нужд ВМС и Армии США. Именно эта платформа должна стать первым наглядным примером нового подхода к автономности дронов. Полноценные летные испытания запланированы на начало 2026 года, когда разработчики намерены продемонстрировать непрерывную подзарядку беспилотника в полете. Если заявленные характеристики будут подтверждены, технология приблизит реализацию концепции "бесконечного полета", способной изменить представления о возможностях беспилотных систем как в военной, так и в гражданской сфере.

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

▪ Одиночество вредит мозгу

▪ Датчик для биометрической аутентификации по дыханию

▪ Революция полимерных диодов приближается

▪ Мобильная батарея I-O Data заряжает два устройства одновременно

▪ Корпус Gigabyte Aorus C500 Glass

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

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

▪ раздел сайта Энциклопедия радиоэлектроники и электротехники. Подборка статей

▪ статья Как получить идеальное видео при кошмарном освещении. Искусство видео

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

▪ статья Удушение и нарушение дыхания. Медицинская помощь

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

▪ статья Обстановка - столы, серванты. Подсобная аппаратура - реквизит. Секрет фокуса

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

www.diagram.com.ua
2000-2026