x-uni.com
регистрация / вход
сейчас на линии 152 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 152 чел.
Компьютерная математика, Теория графов, Часть 2, Волчанская Т.В., Князьков В.С., 2002

Компьютерная математика, Теория графов, Часть 2, Волчанская Т.В., Князьков В.С., 2002

Компьютерная математика, Теория графов, Часть 2, Волчанская Т.В., Князьков В.С., 2002.

  Пособие содержит материал практического изучения основ современной дискретной математики. Приведены основные понятия из теории графов и сетей. Рассматриваются вопросы различных способов описания графов, операции над графами, задачи связности и достижимости в графах. Причем, особое внимание уделено машинным методам представления информации и компьютерным алгоритмам решения задач.
Значительное место уделено решению оптимизационных задач на графах, таких как поиск кратчайших путей в графах и разбиение графов на максимальные сильно связные подграфы.
Учебное пособие предназначено для студентов младших курсов специальностей 20.18.00 , 22.04.00 и других специальностей, изучающих дисциплины “Дискретная математика” и “Прикладная математика”.

Матричный метод разбиения.
Метод разбиения графа на максимальные сильно связные подграфы по матрицам достижимости R и контрдостижимости Q состоит в следующем [5].
1. По матрице смежности строится матрица достижимости R. Используя операцию транспонирования, находим матрицу контрдостижимости Q.
2. Находится матрица C = { сij }, i,j=1,2,3,...,n, где n-число вершин исходного графа , а каждый элемент Cij = rij ∧ gij , т.е. матрица C получается поэлементным логическим умножением матриц R и Q : С = R ∧ Q.
3. Элементы, имеющие одинаковые строки и столбцы в матрице С группируем перестановкой строк и столбцов, получаем блочно диагональную матрицу Св, где каждая группа элементов и есть максимальный сильно связный
подграф.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. ГРАФЫ И СПОСОБЫ ИХ ПРЕДСТАВЛЕНИЯОШИБКА
1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
1.2. СПОСОБЫ ОПИСАНИЯ ГРАФОВ
1.2.1. Теоретико-множественное представление графов
1.2.2. Задание графов соответствием
1.2.3. Матричное представление графов
1.3. ОПЕРАЦИИ НАД ГРАФАМИ
2. ДОСТИЖИМОСТЬ И СВЯЗАНОСТЬ В ГРАФАХ
2.1. МНОГОЗНАЧНЫЕ ОТОБРАЖЕНИЯ
2.1.1. Прямые отображения
2.1.2. Обратные отображения
2.2. ТРАНЗИТИВНЫЕ ЗАМЫКАНИЯ
2.2.1. Прямое транзитивное замыкание
2.2.2. Обратное транзитивное замыкание
2.2.3. Нахождение транзитивных замыканий по матрице смежности
2.3. ДОСТИЖИМОСТЬ И КОНТРДОСТИЖИМОСТЬ
3. ГРАФЫ И ПОДГРАФЫ
3.1 ТИПЫ ГРАФОВ.
3.1.1.Теорема о двудольности
Доказательство.
3.2.ВИДЫ ПОДГРАФОВ
3.3.СИЛЬНО СВЯЗНЫЕ ГРАФЫ И КОМПОНЕНТЫ ГРАФА
4. МЕТОДЫ РАЗБИЕНИЯ ГРАФА НА МАКСИМАЛЬНЫЕ СИЛЬНО СВЯЗНЫЕ ПОДГРАФЫ
4.1 МЕТОД МАЛЬГРАНЖА
4.2. МАТРИЧНЫЙ МЕТОД РАЗБИЕНИЯ
5. ПУТИ И ЦИКЛЫ В ГРАФАХ
5.1. ПУТИ И МАРШРУТЫ
5.2. МАТРИЧНЫЙ МЕТОД НАХОЖДЕНИЯ ПУТЕЙ В ГРАФАХ
5.3. ВЕС И ДЛИНА ПУТИ
5.4. АЛГОРИТМ ДЕЙКСТРЫ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ
5.5. ОРЦИКЛЫ И ЦИКЛЫ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
Приложения
Приложение 1. АЛГОРИТМ НАХОЖДЕНИЯ ХАРАКТЕРИСТИК ГРАФА
Приложение 2. Построение транзитивных замыканий
Приложение 3. Построение матриц достижимости и контрдостижимости
Приложение 4. Разбиение графа на подграфы по методу Мальгранжа
Приложение 5. МАТРИЧНЫЙ МЕТОД РАЗБИЕНИЯ.
ОТВЕТЫ
УПРАЖНЕНИЙ К ГЛАВЕ 1
УПРАЖНЕНИЙ К ГЛАВЕ 2
УПРАЖНЕНИЙ К ГЛАВЕ 3
УПРАЖНЕНИЙ К ГЛАВЕ 4
УПРАЖНЕНИЙ К ГЛАВЕ 5.

Скачать бесплатно на сайте fileskachat.com

Предложения интернет-магазинов

Математика. Теория вероятностей и дискретная математика: Элементы теории, решение задач

Автор(ы): Баюк Олег Александрович, Маркарян Елена Георгиевна   Издательство: Просвещение, 2013 г.  Серия: Сложные темы ЕГЭ

Цена: 333 руб.   Купить

Пособие предназначено учащимся общеобразовательных учреждений (школ, гимназий, колледжей) для углублённого изучения теории вероятностей и связанных с ней разделов дискретной математики (теории множеств, математической логики, комбинаторики, теории графов и математической статистики) в целях успешной сдачи ЕГЭ по математике. В пособии изложены основные теоретические сведения, необходимые для решения задач, приводятся решения типичных заданий ЕГЭ, а также содержатся задания для самостоятельной работы (с ответами, указаниями к решению или решениями). Книга может быть использована в качестве сборника задач на подготовительных курсах, факультативных занятиях, при самостоятельной подготовке к поступлению в вуз и при последующем обучении в вузе.


Информатика. 3 класс. Рабочая тетрадь. В 3-х частях. Часть 1. ФГОС

Автор(ы): Семенов Алексей Львович, Рудченко Татьяна Александровна   Издательство: Просвещение, 2015 г.  Серия: Школа России (ФГОС)

Цена: 211 руб.   Купить

Курс "Информатика" рассчитан на обучение в течение двух лет в объеме 34-68 ч в год. Программа курса предусматривает несколько различных вариантов работы с ним, в том числе как с использованием средств ИКТ, так и бескомпьютерный вариант. Курс издается в трех частях: часть 1 (3 класс), часть 2 (3-4 классы), часть 3 (4 класс). В материалы каждой части курса входит учебник, рабочая тетрадь, тетрадь проектов, компьютерная составляющая и методическое пособие для учителя. Компьютерная составляющая выложена на сайте Единой коллекции цифровых образовательных ресурсов в рамках ИУМК "Информатика 1-4". 4-е издание.


Happy English.ru. 8 класс. Обучающая компьютерная программа. ФГОС (CD)

  Издательство: Титул, 2013 г.

Цена: 461 руб.   Купить

Обучающая компьютерная программа Обучающая компьютерная программа включает лексические и грамматические упражнения, коммуникативные задания и языковые игры, расширяющие и дополняющие материалы учебника и рабочей тетради. Программа предоставляет дополнительные инструменты, расширяющие её функционал, и сохраняет результаты работы учащихся. Программа предназначена для индивидуальной работы на персональном компьютере и может быть использована в качестве домашнего репетитора. Диск содержит 98 упражнений. Рекомендуемая конфигурация компьютера: - Windows ХР, Windows 7 - Pentium 1 ГГц - 512 Мбайт ОЗУ - 16-битная видеокарта и монитор с разрешением 1024x768 - 32-скоростное устройство для чтения компакт-дисков - звуковая карта, наушники / колонки, клавиатура, мышь В виртуальных средах и эмуляторах Windows программа не работает.


Математика. Сценарии уроков. 2 класс. Часть 3. (CD)

  Издательство: Ювента, 2014 г.  Серия: Начальная школа. Математика

Цена: 375 руб.   Купить

Сценарии уроков к учебнику математика автор Петерсон Л.Г. для 2 класса. В комплекте учебник и рабочая тетрадь на диске. Часть 3.

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!