Постановка лабораторной работы по теории графов (алгоритмы и программы) [Описание]

---

запомнить в избранное   искать в этом разделе

---

ВНИМАНИЕ !!! Это сокращенная версия файла. Предназначена она только для того, чтобы вы могли предварительно ознакомиться с документом, перед тем как его скачать. Здесь нет картинок, не сохранен формат, шрифт, размеры и положение на странице.
Чтобы скачать полную версию, нажмите ссылки которые находятся чуть-чуть ниже (Info File Mail)

---

Info File Mail

Файл относится к разделу:
ПРОГРАММИРОВАHИЕ, БАЗЫ ДАHHЫХ

---

Постановка лабораторной работы по теории графов
(алгоритмы и программы)
1. Введение
В последнее время исследования в областях, традиционно относящихся к дискретной математике, занимают все более заметное место. Наряду с такими классическими разделами математики, как математический анализ, дифференциальные уравнения, в учебных планах специальности "Прикладная математика" и многих других специальностей появились разделы по математической логике, алгебре, комбинаторике и теории графов. Причины этого нетрудно понять, просто обозначив круг задач, решаемых на базе этого математического аппарата (см. п.1.3 данного раздела.
1.1 Основные понятия теории графов.
Детальные определения теории графов можно найти в работах [2, 3, 4, 5, 6]. Здесь мы лишь ограничимся перечислением некоторых терминов, которые будут встречаться в дальнейшем, и их кратким описанием.
Граф- непустое множество V и X- некоторый набор пар элементов из V. Элементы множества V называются вершинами, а элементы набора X- ребрами.
Подграф- подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Остовный подграф содержит все вершины графа G.
Связный граф- граф, у которого для любых двух различных вершин существует цепь (последовательность смежных вершин), соединяющая их.
Взвешенный связный граф- связный граф, с заданной весовой функцией (каждому элементу набора X ставится в соответствие некоторое число - вес ребра.
Дерево- связный граф, не содержащий циклов.
Остов- остовный подграф, являющийся деревом.
1.2 Способы задания графов.
Существует ряд способов задания графов. Для решения конкретной задачи можно выбрать тот или иной способ, в зависимости от удобства его применения. Здесь мы перечислим некоторые, наиболее известные способы, дадим их краткую характеристику с точки зрения удобства ввода и обработки на ЭВМ.
Матрица инцидентности- матрица размером (n- число вершин, m- число ребер), элементы которой равны 1, если i-я вершина инцидентна j-му ребру, и 0

• подписаться на рассылку. • добавить в избранное. • нашли ошибки ?

Это место