На бирже курсовых и дипломных проектов можно найти образцы готовых работ или получить помощь в написании уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ, диссертаций, рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Работа № 92986


Наименование:


Курсовик Основные понятия теории графов.Виды графов

Информация:

Тип работы: Курсовик. Добавлен: 8.12.2015. Сдан: 2015. Страниц: 33. Уникальность по antiplagiat.ru: < 30%

Описание (план):



Оглавление
Введение 3
Основные понятия и определения 4
Виды графов 6
Подграфы и наследственные свойства графов 7
Способы задания графов 8
Операции над графами. 11
Деревья 12
Доминирование. Внутренняя и внешняя устойчивость в графах. Ядро графа 14
Практическая часть. Примеры применения графов. 16
Задача 1 16
Задача 2. 16
Задача 3 18
Задача 4 25
Заключение. 33
Список используемой литературы 34



Введение
Теория графов - один из разделов дискретной математики, анализирующий различные потоки (товарные, денежные, информационные, материальные), представляя их в виде сетей (совокупности вершин и дуг). Основной особенностью теории графов является геометрический подход к изучению объектов.
Обладая свойством наглядности (основное преимущество перед другими методами исследования операций), теория графов предлагает исследователю не только простой, но и доступную и эффективную помощь в построение моделей экономики.


Впервые понятие «граф» появилось в 1936 году, его ввел венгерский математик Денеш Кёнинг. Но в истории известна более ранняя работа по теории графов, которая была представлена в 1736 году Леонардом Эйлером, где он решил «задачу о Кёнигсбергских мостах». В этой задачи было необходимо обойти семь мостов центральной части города Кёнигсберг, пройдя по каждому лишь один раз, и вернуться в исходную точку. Схема города и решение этой задачи представлены ниже (рисунок 1). Эйлер в своем решении доказал, что невозможно обойти 7 городских мостов и прийти в начальную точку, при условии, что можно пройти по каждому мосту ровно один раз.
Теория графов носит ярко выраженную прикладную направленность.
Теория графов стала одной из существенных частей математического аппарата многих научных дисциплин, таких как: машинная математика, теория информации, исследование операций, биология, математическая лингвистика, то есть таких дисциплин, в задачах которых главным является рассуждения и построения дискретно-комбинаторного характера.


Основные понятия и определения
Пускай S - непустое конечное множество. Обозначу множество всех его двухэлементных подмножеств V(2).
Графом (или псевдографом) G называется пара множеств G=(S,U), где U - произвольное подмножество множества V(2). При этом пишется G=(S,U).
Вершины графа G - элементы множества S, а ребра - элементы множества U.
Самым простым примером может служить схема метрополитена, где вершины графа - станции метро, а ребрами являются - пути между станциями.
Пустым граф (нуль-графом) G=(S,U) называется, если U = ?.
Порядок - число вершин графа G=(S,U). В том случае, когда порядок графа равен n, то записывается в виде: |G|=n.
Через (x,y) буду обозначать двухэлементное подмножество множества S, которое принадлежит U и состоит из элементов x и y.
Петли - ребра вида (x,x).
Одинаковые пары из множества U называются кратными (параллельными) ребрами.
Граф, содержащий петли и кратные ребра, называется графом с кратными ребрами и петлями.
Мультиграф (или графом с кратными ребрами) - граф, у которого нет петель.
Простым графом считается мультиграф, не содержащий кратных ребер.
Таким образом, в простом графе нет петель и кратных ребер.
Графы может представить в виде графической интерпретации - диаграмм, которые состоят из точек и линий. Точки соответствуют вершинам графа, а линии - ребрам.
Сумма степеней вершин (x,y) вычисляется по правилу: удваивается число ребер этого графа.
Следствие. В любом графе количество вершин нечетной степени четно.
Ориентированный (направленный) граф - граф, у которого пары во множестве U упорядоченные.
Ребра ориентированного графа называются дугами (ориентированными ребрами).
Другими словами ориентированный граф - граф, состоящий из множества вершин и дуг.
Началом называется вершина x дуги (x,y), а вершина y - ее концом. В этом случае говорят, что духа (х,у) исходит их вершины x и входит в вершину y.
Длина пути - сумма длин дуг, входящих в этот путь.
На диаграммах ориентированных графов обычно направления дуг отмечаются стрелками.
Пару (S,U) называют неориентированным графом G, в котором S - множество вершин, а U - множество ребер, являющееся подмножеством множества V(2). . Иначе это определение формулируется так: граф (S,U) называется неориентированный, в том случае, когда S является непустым множеством вершин, а U - это множество, состоящее из неупорядоченных пар различных элементов, взятых из S, называемые ребрами.
Если (x,y) - неупорядоченная пара, то ребро (x,y) называется неориентированным, а вершины x и y называются концами неориентированного ребра(x,y). Говорят также, что вершины смежны. Про ребро и вершину, которая является концом, говорят, что они инцидентны.


Например, на данном графе вершины v1 и v2 смежны, а вершины v1 и v5 не смежны. Ребра {v1,v2} и {v1,v3} смежны, а ребра {v4,v5} и {v2,v3} не смежны. Вершина v3 и ребро {v2,v3} инцидентны.
Число ребер, инцидентных вершине x, определяет степень вершины, которая обозначается deg x. Так, в данном графе получается, что deg v1=deg v2=deg v3=deg v4=3, a deg v5=2. Вершину называют изолированной, если степень ее вершины =0, и концевой (висячей) если deg x=1.
Сумма степеней вершин (x,y) графа - удвоенное число его ребер.
Следствие. В любом графе число вершин нечетной степени четно.
Полустепенью исхода (захода) вершины xi ориентир........


Список используемой литературы
1. Лекции по дискретной математике. В.Б.Гисин.
2. Теория графов в задачах и упражнениях. В.А.Емеличев, И.Э.Зверович.
3. Элементы теории графов. Учебное пособие. Л.Н.Домнин.
4. Теория графов. Д.В. Карпов.



Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы

* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.