Метрические характеристики графа

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ РОСИЙСКОЙ ФЕДЕРАЦИИ

Государственное Образовательное Учреждение Высшего Профессионального Образования «Воронежский Государственный Технический Университет» (ГОУВПО «ВГТУ»)

Кафедра: Высшей математики и физико-математического моделирования

КУРСОВАЯ РАБОТА

по дисциплине «Математика»

«Метрические характеристики графа»

Выполнил: студент группы

РК-051 Жищенко С.А.

Руководитель: Ускова Н.Б.

Оценка:

Дата защиты:

Воронеж 2006 г.

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ РОСИЙСКОЙ ФЕДЕРАЦИИ

Государственное Образовательное Учреждение Высшего Профессионального Образования «Воронежский Государственный Технический Университет» (ГОУВПО «ВГТУ»)

Кафедра: Высшей математики и физико-математического моделирования

Задание на курсовую работу по дисциплине «Математика»

Исполнитель: Жищенко С.А.

Руководитель: Ускова Н.Б.

«Метрические характеристики графа»

Тема курсовой работы утверждена постановлением по РТФ от 3.10.06, №6.

Задание: дано два графа, построить их матрицы смежности и инцидентности, определить их метрические характеристики.

Срок выдачи курсовой работы:

Срок сдачи:

Задание принял ст. гр. РК-051 Жищенко С.А.

Руководитель__________

Воронеж, 2006.

Содержание

Понятие «граф»..........................................................................................5

Матричное представление графов............................................................9

Операции над графами..............................................................................11

Маршруты, цепи, циклы............................................................................12

Метрические характеристики графа.........................................................15

Приложение теории графов в различных областях науки и техники...16

Практическая часть....................................................................................18

Листинг программы...................................................................................21

ПОНЯТИЕ "ГРАФ"

Пусть V – непустое множество, V(2) – множество всех его двухэлементных подмножеств. Пара (V,E), где E – произвольное подмножество множества V(2) , называется графом (неориентированным графом). Элементы множества V называются вершинами графа, а элементы множества E – ребрами. Итак, граф – это конечное множество V вершин и множество E ребер, E⊂V(2) .

Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.).

Множества вершин и ребер графа G обозначается соответственно VG и EG. Вершины и ребра графа называются его элементами. Число |VG| вершин графа G называется его порядком и обозначается |G|.

Если |G|=n,|EG|=m, то граф называют (n, m)-графом.

Говорят, что две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если e={u, v}– ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v.

Два ребра называются смежными, если они имеют общий конец.

Вершина v и ребро e называются инцидентными, если v является одним из концов ребра e, и не инцидентными в противном случае.

Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.

Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается NG(v) или просто N(v).

Графы удобно изображать в виде рисунков (геометрических графов). Геометрический граф в пространстве n-мерном евклидовом пространстве εn есть множество точек пространства εn и множество E простых кривых, таких: 1) что каждая замкнутая кривая в E содержит только одну точку v множества V; 2) каждая незамкнутая кривая в E содержит ровно две точки множества V, которые являются ее граничными точками; 3) кривые в E не имеют общих точек кроме точек из множества V. При этом точки множества V соответствуют вершинам графа, а соединяющие пары точек линии – ребрам.

Граф G называется полным, если любые две его вершины смежны. Полный граф порядка n обозначается Kn.

Граф называется вырожденным (пустым), если любые две его вершины не смежны (т.е. у него нет ребер).

Пусть G и H графы, а ϕ: VG→VH – биекция. Если для любых вершин u и v их образы ϕ(u) и ϕ(v) смежны в H тогда и только тогда, когда u и v смежны в G, то эта биекция называется изоморфизмом графов G и H, асами графы G и H – изоморфными. Изоморфные графы будем обозначать G≅H (атакже HG).

Если граф G изоморфен геометрическому графу G', то G' называется геометрической реализацией графа G.

Очевидно, что отношение изоморфизма графов является эквивалентностью. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т.е. считать совпадающими (их можно изобразить одни

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать