x-uni.com
x-uni.com
x-uni.com
Математика
Биология
Литература
Русский язык
География
Физика
Химия
История
Английский
Информатика
География
Информатика
Компьютерная математика, Теория графов, Часть 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.

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

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

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

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

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


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

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

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

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


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

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

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

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


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

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

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

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