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.04.2026

Вопрос о том, как и насколько быстро меняется человеческий вид, давно занимает биологов и генетиков. Долгое время считалось, что эволюционные процессы происходят крайне медленно, однако новые данные заставляют пересматривать эти представления. Особенно интересные результаты связаны с изменением частоты редких генетических признаков, включая рыжий цвет волос. Рыжеволосость сегодня остается редкой чертой: ее носители составляют менее 2 процентов мирового населения. Однако анализ древней и современной ДНК показывает, что ген, связанный с этим признаком, за последние примерно 10 тысяч лет стал заметно более распространенным, особенно среди популяций Европы. Более того, вместе с ним исследователи фиксируют и другие изменения в генетическом профиле человека, затрагивающие внешность и физиологические особенности. Среди сопутствующих тенденций, выявленных в генетических данных, отмечается увеличение частоты светлой кожи, снижение вероятности мужского облысения, а также некоторые физиолог ...>>

Нейтринный лазер 30.04.2026

Нейтринный лазер - это гипотетическое устройство, способное управлять потоками одних из самых трудноуловимых частиц во Вселенной. Такая разработка открывает новые горизонты в изучении фундаментальных законов природы и может изменить представления о космосе. Идею нового типа излучателя представили физики из Massachusetts Institute of Technology, предложив лазер, который вместо света генерирует поток нейтрино. Эти частицы, почти не взаимодействующие с материей, настолько слабо проявляют себя, что их часто называют "частицами-призраками". Тем не менее они пронизывают все вокруг: по оценкам, триллионы нейтрино ежесекундно проходят через человеческое тело, не оставляя следа. Несмотря на их колоссальную распространенность во Вселенной, нейтрино остаются одними из наименее изученных частиц. Их крайне сложно регистрировать, а еще сложнее контролировать, поэтому традиционно их получают в крупных установках вроде ядерных реакторов или ускорителей частиц. Такие комплексы требуют огромных за ...>>

Мороженое не такое вредное, как принято считать 29.04.2026

В питании часто встречаются продукты, которые одновременно вызывают удовольствие и сомнения с точки зрения здоровья. К таким относится и мороженое: оно воспринимается как типичный десерт с высоким содержанием сахара и жиров, однако современные научные данные постепенно усложняют это привычное представление. Долгое время считалось, что мороженое не может быть частью рационального питания, однако исследования последних лет показывают более неоднозначную картину. Ученые подчеркивают, что влияние этого продукта на организм зависит не только от его сладости или калорийности, но и от состава, качества ингредиентов и общего образа жизни человека. Одни из наиболее масштабных данных были получены в рамках долгосрочных наблюдений в США, включавших проекты Nurses Health Study, Nurses Health Study II и Health Professionals Follow-Up Study. В этих исследованиях на протяжении 20-40 лет наблюдали примерно 190 тысяч взрослых участников, регулярно собирая данные об их питании, физической активнос ...>>

Случайная новость из Архива Магнит превращает материал из мягкого в твердый 07.12.2018 Разработан метаматериал, ведущий себя совершенно не так, как природные материалы, из которого могут быть созданы роботы или спортивные шлемы нового поколения. Метаматериал представляет собой сеть пластиковых трубок, заполненных жидкостью, которая становится более вязкой в магнитном поле, в результате чего трубки уплотняются. Кристофер Спадаччини, инженер по материалам в Ливерморской национальной лаборатории им. Лоуренса в Калифорнии, и его коллеги напечатали на 3-D принтере решетки, состоящие из пластиковых стоек длиной 5 миллиметров, и ввели в них смесь мелких частиц железа и масла. В отсутствие магнитного поля железные микрочастицы оставались беспорядочно разбросанными по всему маслу. Но под воздействием магнита эти железные микрочастицы выстраивались в цепочки вдоль силовых линий магнитного поля, делая жидкость более вязкой, а решетки более жесткими. Твердый кусок материала, наполненного железными микрочастицами, был бы тяжелым и дорогим в изготовлении. По словам соавтора Джулии Джексон, инженера из Ливеморской лаборатории, создание трубчатых конструкций делает этот изменяемый материал более легким. Исследователи проверили отдельные "элементарные ячейки" нового материала - полые структуры, которые в совокупности могут образовывать крупные решетки. Если ячейка находилась на расстоянии 8 см от магнита, а затем ее перемещали на расстояние 1 см от магнита, то жесткость структуры увеличивалась примерно на 62 процента. В будущих технологиях этот материал может быть соединен с устройствами, которые используют электричество для генерации магнитных полей, называемыми электромагнитами. По словам Джексона, материал, который способен становиться при необходимости мягче или жестче, может быть использован для изготовления спортивных накладок или шлемов следующего поколения с настраиваемым поглощением ударов. Роботы с изменяемой жесткостью могут втискиваться в небольшие пространства, но при этом быть достаточно крепкими, чтобы перемещать другие объекты.

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

▪ Новый рекорд длительности термоядерного синтеза

▪ Суперурожайный рис

▪ Векторные модуляторы AD8340 и AD8341

▪ Первые масляные картины

▪ Миноискатель онколога

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

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

▪ раздел сайта Детекторы напряженности поля. Подборка статей

▪ статья Фиговый листок. Крылатое выражение

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

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

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

▪ статья Кабели коаксиальные отечественные РК75-1-11 - РК75-3-22. Энциклопедия радиоэлектроники и электротехники

[an error occurred while processing this directive] Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2026