Алгоритмы на графах. Независимые и доминирующие множества
Состав работы
|
|
|
|
Работа представляет собой zip архив с файлами (распаковать онлайн), которые открываются в программах:
- Microsoft Word
Описание
Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V, E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, – ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.
Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.
Матрица смежности – это двумерный массив размерности N*N.
A [i, j]=
Для хранения перечня ребер необходим двумерный массив R размерности M*2. Строка массива описывает ребро.
Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.
Матрица смежности – это двумерный массив размерности N*N.
A [i, j]=
Для хранения перечня ребер необходим двумерный массив R размерности M*2. Строка массива описывает ребро.
Похожие материалы
Динамическое программирование, алгоритмы на графах
Qiwir
: 6 октября 2013
Содержание
Введение
1. Алгоритмы, использующие решение дополнительных подзадач
2. Основные определения теории графов
3. Поиск пути между парой вершин невзвешенного графа
4. Пути минимальной длины во взвешенном графе
Заключение
Литература
Введение
Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулиро
10 руб.
Алгоритм раскраски графа (точный)
alfFRED
: 15 августа 2013
СОДЕРЖАНИЕ
Аннотация
1. Теоретическая часть
2. Алгоритм, использующий метод Магу - Вейссмана
2.2 Разработанный алгоритм
3. Описание программы
3.1 Общие сведения
3.2 Вызов и загрузка
3.3 Функциональное назначение
3.4 Описание логической структуры программы
3.5 Инструкция пользователю
3.6 Решение контрольных примеров
Заключение
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ
Аннотация
В настоящей пояснительной записке приведено описание алгоритма раскраски графа (точный). Изложены вопросы проектирова
Алгоритмы на графах. Кратчайшие расстояния на графах
alfFRED
: 3 октября 2013
Содержание
Введение
1 Поиск в глубину
2 Задача "Дороги"
3 Задача "Перекрестки"
4 Задача "Скрудж Мак-Дак"
Заключение
Литература
Введение
Прежде всего, несколько слов о том, как возникает понятие графа из естественных условий задач. Приведем несколько примеров.
Пусть мы имеем карту дорог, в которой для каждого города указано расстояние до всех соседних с ним. Здесь два города называются соседними, если существует дорога, соединяющая непосредственно эти два города.
Аналогично, можно расс
10 руб.
Модификация алгоритма определения клик графа с параметрической адаптацией
evelin
: 30 сентября 2013
Кликой графа называется максимальный полный подграф, который не входит ни в один полный подграф более высокого порядка /1/ .
Под точностью решения задачи определения клик графа будем понимать количество выделенных клик. При этом, если выделены все клики графа, то точность решения равна 100%.
Рассматривается класс нериентированных графов без петель и кратных ребер.
Комбинаторная сложность точных алгоритмов определения клик графа приводит к необходимости использовать приближенные методы при реш
15 руб.
Лабораторной работе №4. Алгоритмы и структуры данных. Тема: Графы. ЛЭТИ.
DiKey
: 23 марта 2023
Лабораторной работе №4. Алгоритмы и структуры данных.
Тема: Графы. ЛЭТИ.
Вариант 35
Содержание
Введение ........................................................................................................ 3
Задание ........................................................................................................... 3
Постановка задачи и описание решения ..................................................... 3
Контрольные тесты ..........................................................
75 руб.
Графы. Нахождение кратчайшего расстояния между двумя вершинами с помощью алгоритма Дейкстры
uksne
: 22 января 2011
ЛАБОРАТОРНАЯ РАБОТА №4 по дисциплине «Теория сложностей вычислительных процессов и структур».
Графы. Нахождение кратчайшего расстояния между двумя вершинами с помощью алгоритма Дейкстры
Вариант №10
Задание:
Написать программу, которая по алгоритму Дейкстры находит кратчайшее расстояние от указанной вершины до всех остальных вершин связного взвешенного неориентированного графа, имеющего 6 вершин (нумерация вершин начинается с 0). Граф задан матрицей весов дуг, соединяющих всевозможные пары вершин
100 руб.
Лабораторная работа №6. Структуры и алгоритмы обработки данных. Нахождение кратчайших путей в графе. Алгоритм Дейкстры.
DiKey
: 30 июня 2022
Лабораторная работа №6. Структуры и алгоритмы обработки данных. Нахождение кратчайших путей в графе. Алгоритм Дейкстры.
Постановка задачи:
Найти кратчайший путь между двумя фиксированными вершинами заданного графа с помощью алгоритма Дейкстры.
Теория
Задача о кратчайшем пути – задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Алгоритм нахождения кратчайшего пути между двумя фиксированными вершин
75 руб.
Лабораторная работа №4. Структуры и алгоритмы обработки данных. Поиск в глубину в графе.
DiKey
: 30 июня 2022
Лабораторная работа №4. Структуры и алгоритмы обработки данных. Поиск в глубину в графе.
Постановка задачи:
Задан граф. Осуществить прохождение вершин заданного графа в соответствии с обходом этого графа согласно алгоритму «Поиск в глубину» в порядке возрастания первоначальной нумерации вершин графа.
Алгоритм прохождения вершин графа
1. Заносим в стек первую вершину.
2. Заносим в список посещенных первую вершину.
3. Выделяем визуально первую вершину.
4. Пока количество элементов в стеке больше
75 руб.
Другие работы
Налоговые вычеты по отдельным видам доходов
DocentMark
: 28 октября 2013
В последнее время словосочетание "налоговый вычет" все чаще слышится в обществе. Однако далеко не все понимают, что такое налоговый вычет, в каких случаях он предоставляется. Получая зарплату или иной доход, мы обязаны уплатить налог на доходы физических лиц. Как правило, бухгалтерия организации сама удерживает его в размере 13 % от суммы — налоговой базы. Таким образом, на руки нам выдают наш заработок на 13 % меньше. Удержанная сумма идет в фонды пенсионного, социального и обязательного медици
5 руб.
Электронная торговля экономическая сущность и значение в мировой экономике
alfFRED
: 7 ноября 2013
Содержание
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .стр. 3-4
Глава 1. Понятие и сущность электронной торговли . . . . . . . . . . . . .стр. 5-10
1.1Определение электронной торговли. . . . . . . . . . . . . . . . . . . . . стр. 5-7
1.2 Классификация и стадии электронной торговли. . . . . . . . . . .стр. 7-8
1.3 Субъекты и направление взаимодействий субъектов . . . . . . стр. 8-9
1.4 Виды электронной торговли и их особенности .
10 руб.
Тепломассообмен ТГАСУ 2017 Задача 1 Вариант 29
Z24
: 2 февраля 2026
Определение мощности электронагревателя для обогрева помещения
Две стены помещения с внутренними размерам, (1 ‒ a·h и 2 ‒ b·h) выложены из красного кирпича толщиной δкп, изолированного с наружной стороны сайдингом толщиной δсд, а с внутренней покрыта слоем штукатурки толщиной δшт.
3 и 4-я стены с размерами (3 ‒ b·h и 4 ‒ a·h) выполнены из панелей толщиной δпн, оштукатуренных с обеих сторон штукатуркой толщиной δшт. Пол и потолок выполнены из железобетонных плит толщиной δжб, где а – длина,
200 руб.
Основы администрирования сетевых устройств. Лабораторная работа №3. "Настройка статической и динамической маршрутизации. Настройка SNMP-мониторинга". Вариант №6.
glebova95
: 11 сентября 2021
Основы администрирования сетевых устройств. Лабораторная работа 3. "Настройка статической и динамической маршрутизации.
Настройка SNMP-мониторинга". Вариант 6.
Цель работы:
1. Приобретение навыков в администрировании статической маршрутизации и
динамической маршрутизации по протоколу RIP.
2. Приобретение навыков администрирования SNMP-мониторинга.
Задачи для ЛР-3:
1. Запустить сохраненный из предыдущей работы файл со всеми настройками для Вашего
варианта схемы рис. 1.1.
2. Проверить сохранность
120 руб.