Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте za4eti.ru

Математика Математика

Графы. решение практических задач с использованием графов (С++)

Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10
Забавная пачка "5000 дублей".
Юмор – настоящее богатство! Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь
60 руб
Раздел: Прочее

Курсовая работа Выполнил: студент 1-го курса  факультета КНиИТ, группа № 121, Жучков Андрей Сергеевич Саратовский государственный университет  им. Н.Г. Чернышевского Кафедра теоретических основ информатики и информационных технологий Саратов 2005 Введение В последнее время исследования в областях, традиционно относящихся к дискретной математике, занимают все более заметное место. Наряду с такими классическими разделами математики, как математический анализ, дифференциальные уравнения, в учебных планах специальности "Прикладная математика" и многих других специальностей появились разделы по математической логике, алгебре, комбинаторике и теории графов. Причины этого нетрудно понять, просто обозначив круг задач, решаемых на базе этого математического аппарата. История возникновения теории графов. Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач. Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году. рис. 1  Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году. рис. 2 Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно.

Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно. Рис. 3 Основные понятия теории графов Графом G(V,E) называется совокупность двух множеств – непустого множества V(множества вершин) и множества E двухэлементных подмножеств множества V(E – множество ребер). Ориентированным называется граф, в котором  - множество упорядоченных пар вершин вида (x,y), где x называется началом, а y – концом дуги. Дугу (x, y) часто записывают как . Говорят также, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x. Если элементом множества E может быть пара одинаковых (не различных) элементов V, то такой элемент множества E называется петлей, а граф называется графом с петлями (или псевдографом). Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом. Если элементами множества E являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества E называются гипердугами, а граф называется гиперграфом. Если задана функция F : V → M и/или F : E → M, то множество M называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным. Подграфом называется граф G′(V′,E′), где и/или . Если V′ = V, то G′ называется остовным подграфом G. Если , то граф G′ называется собственным подграфом графа G. Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержит все возможные рёбра G. Степень (валентность) вершины – это количество ребер, инцидентных этой вершине (количество смежных с ней вершин). Маршрутом в графе называется чередующаяся последовательность вершин и ребер , в которой любые два соседних элемента инциденты. Если , то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл – контуром. рис. 4. Маршруты, цепи, циклы Пример В графе, диаграмма которого приведена на рис.4: v1, v3, v1, v4 – маршрут, но не цепь; v1, v3, v5, v2, v3, v4 – цепь, но не простая цепь; v1, v4, v3, v2, v5 – простая цепь; v1, v3, v5, v2, v3, v4, v1 – цикл, но не простой цикл; v1, v3, v4, v1 – простой цикл. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом. Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом. Деревом называется связный граф без циклов. Остовом называется дерево, содержащее все вершины графа. Паросочетанием называется множество ребер, в котором никакие два не смежны.

Паросочетание называется максимальным, если никакое его надмножество не является независимым. Две вершины в графе связаны, если существует соединяющая их простая цепь. Граф, в котором все вершины связаны, называется связным. Граф, состоящий только из изолированных вершин, называется вполне несвязным. Длиной маршрута называется количество ребер в нем (с повторениями). Расстоянием между вершинами u и v называется длина кратчайшей цепи , а сама кратчайшая цепь называется геодезической. Диаметром графа G называется длина длиннейшей геодезической. Эксцентриситетом вершины v в связном графе G(V,E) называется максимальное расстояние от  вершины v до других вершин графа G. Радиусом графа G называется наименьший из эксцентриситетов вершин. Вершина v называется центральной, если ее эксцентриситет совпадает с радиусом графа. Множество центральных вершин называется центром графа. рис. 5 Эксцентриситеты вершин и центры графов (выделены). Основные теоремы теории графов Опираясь на приведенные выше определения теории графов, приведем формулировки и доказательства теорем, которые затем найдут свои приложения при решении задач. Теорема 1. Удвоенная сумма степеней вершин любого графа равна  числу его ребер. Доказательство. Пусть А1, А2, А3, ., A — вершины данного графа, a p(A1), p(А2), ., p(A ) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это равносильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины). Отсюда следует: p(A1) p(А2) . p(A )=0,5 , или 2(p(A1) p(А2) . p(A ))= , где — число ребер. Теорема 2. Число нечетных вершин любого графа четно. Доказательство. Пусть a1, a2, a3, , ak — это степени четных вершин графа, а b1, b2, b3, , bm — степени нечетных вершин графа. Сумма a1 a2 a3 ak b1 b2 b3 bm ровно в два раза превышает число ребер графа. Сумма a1 a2 a3 ak четная (как сумма четных чисел), тогда сумма b1 b2 b3 bm должна быть четной. Это возможно лишь в том случае, если m — четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать. Эта теорема имеет немало любопытных следствий. Следствие 1. Нечетное число знакомых в любой компании всегда четно. Следствие 2. Число вершин многогранника, в которых сходится нечетное число ребер, четно. Следствие 3. Число всех людей, когда-либо пожавших руку другим людям, нечетное число раз, является четным. Теорема 3. Во всяком графе с вершинами, где больше или равно 2, всегда найдутся две или более вершины с одинаковыми степенями. Доказательство. Если граф имеет вершин, то каждая из них может иметь степень 0, 1, 2, ., ( -1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А — изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)= -1. В самом деле, эта вершина должна быть соединена с ( -1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем вершин, не могут быть одновременно вершины степени 0 и ( -1).

Объекты познания, с точки зрения прагматизма, формируются познавательными усилиями в ходе решения практических задач; мышление - средство для приспособления организма к среде с целью успешного действия; понятия и теории инструменты, орудия; истина толкуется в прагматизме как практическая полезность. Возник в 70-х гг. 19 в. в США; основные идеи высказал Ч. Пирс, доктрину разрабатывали У. Джемс, Дж. Дьюи, Ф. К. С. Шиллер, Дж. Г. Мид. ПРАГМАТИКА - раздел семиотики, в котором изучаются отношения субъектов, воспринимающих и использующих какую-либо знаковую систему, к самой знаковой системе. Основные идеи выдвинул Ч. Пирс, развиты Ч. Моррисом (ввел самый термин). Идеи прагматики применяются для разработки эвристического программирования, машинного перевода, информационно-поисковых систем и др. ПРАГМАТИЧЕСКАЯ САНКЦИЯ 1713 - закон о престолонаследии в австрийской монархии Габсбургов, изданный Карлом VI. Устанавливал нераздельность габсбургских земель, разрешал их наследование дочерями монарха при отсутствии у него сыновей

1. Обучение решению математических задач с помощью графов

2. Графы. решение практических задач с использованием графов (С++)

3. Основополагающие принципы андрагогической модели обучения: Оптимальные условия их применения

4. Применение новейших экономико-математических методов для решения задач

5. Исследование несостоятельности (банкротства) предприятия с применением статистических и математических методов анализа

6. Математическое моделирование и расчет систем управления техническими объектами
7. Оздоровительная ходьба - оптимальное начало здорового образа жизни
8. Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных

9. Математическое моделирование высокочастотных радиоцепей на основе направленный графов

10. Поиск оптимального пути в графе

11. Министр просвещения граф С. С. Уваров. Самодержавие, Православие, Народность

12. Работа с графами

13. Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем

14. Поиск клик в графах

15. Теория графов. Задача коммивояжера

16. Алмаз-графит

Подгузники-трусики для девочек Huggies DryNights, 8-15 лет, 9 штук.
Деликатная защита на всю ночь для детей от 4х лет, страдающих энурезом. Одноразовые Трусики Хаггис Драйнайтс для девочек 8-15 лет (30 - 47
427 руб
Раздел: Обычные
Тетрадь общая с магнитной закладкой "FLUOR. Желтый", В5, 120 листов, клетка.
Формат - В5. Закладка - ляссе. Внутренний блок - офсет, клетка. Обложка - мелованный картон. Скрепление - книжный переплет. Отделка -
418 руб
Раздел: Прочие
Настольная игра "На память".
Следите за тем, в каком порядке загораются кнопки, а затем правильно повторите последовательность загоравшихся цветов! Отличная игра,
310 руб
Раздел: Прочие

17. Поліграфічна промисловість України. II роль та перспективи розвитку

18. Невольник чести (о графе Михаиле Воронцове)

19. Графы

20. Применение информатики, математических моделей и методов в управлении

21. Линейные симметрии многогранника паросочетанийи автоморфизмы графа

22. Математические модели и методы обоснования управленческих решений и сферы их применения в практике управления
23. Аллотропные видоизменения углерода: графит и алмаз
24. Граф Алексей Андреевич Аракчеев

25. Реакторный графит: разработка, производство и свойства

26. Графічний планшет Wacom Graphire

27. Модели теории графов для выделения контуров по градиентному изображению

28. Поиск в ширину на графах

29. Эйлеровы и гамильтоновы графы

30. Aлгоритмы на графах

31. Александр Дюма. Граф Монте-Кристо

32. «Мысль семейная»: роман графа Л.Н. Толстого «Анна Каренина»

Подставка для ножей AK-210ST "Alpenkok", 11x22 см.
Размеры: 11х22 см. Подставка для ножей мраморной расцветки с черным наполнением. Материал корпуса: пластик. Внутренняя часть:
673 руб
Раздел: Подставки для ножей
Колокольчик декоративный "Узор", 8x13 см.
Цвет: белый. Материал: фарфор. Размер: 8x13 см.
355 руб
Раздел: Миниатюры
Горшок надувной для дома и авто "Baby-Krug", розовый.
Невероятно удобный надувной горшок был разработан при непосредственном участии квалифицированных медицинских работников и технических
489 руб
Раздел: Горшки обычные

33. «Война и мир»: главная книга графа Л.Н. Толстого

34. Способи і заходи захисту від шуму в поліграфії

35. Алмаз и графит: свойства, значение, происхождение

36. Применение методов математической статистики и теории вероятностей в задачах теоретической лингвистики при анализе устной и звучащей речи на русском и английском языках

37. Алгоритмы на графах. Кратчайшие расстояния на графах

38. Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему
39. Бібліотека ASM-86 для перегляду графіки в стандартах BMP та PCX
40. Вирізання картинок з екрану та запис їх в BMP форматі (для графіки) і TXT форматі (для тексту)

41. Відображення на екрані дисплея графічної інформації

42. Концепції програмування. Графічна система OpenGL

43. Определение связности графа на Лиспе

44. Отримання зображень з допомогою комп’ютерної графіки

45. Побудова ліній та точок з допомогою комп’ютерної графіки

46. Проектування керуючих автоматів Мура та Мілі за заданою граф-схемою алгоритму

47. Статистичне моделювання сітьового графіка побудови судна

48. Дослідження графіку функції y=cos(x)*ln(x)

Увлекательная настольная игра "Этажики", новая версия.
На игровом поле две карты — карта с этажом, на котором находятся игроки, и карта с воздушным шаром. Шар перемещает всех на определённое
632 руб
Раздел: Карточные игры
Магнитный театр "Колобок".
Увлекательное театральное представление с любимыми героями русской народной сказки «Колобок» и вашим ребенком в роли главного режиссера.
308 руб
Раздел: Магнитный театр
Компрессор для подкачки шин С-12.
Автокомпрессор — это электрическое устройство, предназначенное для накачивания шин на колесах. В отличие от механического насоса, при
732 руб
Раздел: Насосы, компрессоры автомобильные

49. Графічна бібліотека OpenGl

50. Графічне та геометричне моделювання та інтерактивні системи» На тему «Система бухгалтерського обліку»

51. Графічні роботи на комп’ютері

52. Автоматизація графічних та розрахункових задач проектування

53. Вивчення епіграфічних колекцій у музеях

54. Застосування поліграфічної продукції у політичній рекламі
55. Графы
56. Графы. Основные понятия

57. Інженерна графіка

58. Применение математических методов при обновлении парка автотранспортного предприятия

59. Автоматизація графічних та розрахункових задач проектування. Проектування офісу математики

60. Графічні методи розв’язування задач із параметрами

61. Каліграфія в школі

62. Організація та методика проведення уроку з теми: "Векторний графічний редактор Corel Draw"

63. Реалізація шляхів естетичного виховання першокласників у процесі формування каліграфічної навички

64. Шляхи формування навичок каліграфічного письма

Портфель "Attache", A4, серый.
Одно отделение.
375 руб
Раздел: Папки-портфели, папки с наполнением
Пенал-книжка для начальной школы "Ever After High", 21x14 см.
Пенал-книжка для начальной школы. 1 отделение, держатели письменных принадлежностей. Застегивается на молнию. Размер: 21х14х3 см.
303 руб
Раздел: Без наполнения
Набор инструментов.
Помогаю папе - отличный игровой набор для юных мастеров. Научит начальным профессиональным навыкам. Поможет ребенку почувствовать себя
589 руб
Раздел: Инструменты и мастерские

65. Расчет обмотки статора трехфазного асинхронного двигателя при наличии магнитопровода с применением ЭВМ

66. Метод графо-аналитических зависимостей в налоговом менеджменте

67. Структура графа состояний клеточных автоматов определённого типа

68. Применение математического моделирования в экономике

69. Капитальный ремонт пути на щебеночном балласте с укладкой железобетонных шпал с применением машин тяжелого типа

70. Применение фильтра Калмана в задаче идентификации отказов двигателей стабилизации космического аппарата
71. Применение лазеров в военном деле
72. Зажигательные смеси, состав, средства применения и доставки, вызываемые повреждения, методы лечения и защиты

73. Характеристика современных средств поражения и последствия их применения

74. Механизм применения антимонопольных законов

75. Применение норм права

76. Дисциплинарная ответственность. Применение дисциплинарного взыскания

77. Проект учета пользовательских счетов для интернет-провайдеров на базе OS FreeBSD с применением программы "Billing ISP"

78. Определение эффективности применения информационной технологии

79. Применение ЭВМ в управлении производством

80. Организация и применение микропроцессорных систем обработки данных и управления

Подгузники-трусики для мальчиков Huggies DryNights, 8-15 лет, 9 штук.
Деликатная защита на всю ночь для детей от 4х лет, страдающих энурезом. Одноразовые Трусики Хаггис Драйнайтс для мальчиков 8-15 лет (30-57
468 руб
Раздел: Обычные
Глобус "Двойная карта" рельефный, с подсветкой, на подставке из пластика.
Диаметр: 250 мм. Масштаб: 1:50000000. Материал подставки: пластик. Цвет подставки: прозрачный. Мощность: 220 V, переключатель на шнуре;
1072 руб
Раздел: Глобусы
Фломастеры "631", 50 цветов.
Яркие фломастеры с коническим наконечником диаметром 5 мм, можно использовать для рисования тонких линий 0,75 мм или более толстых до 3
658 руб
Раздел: Более 24 цветов

81. Применение самоорганизующихся карт Кохонена для классификации и анализа пространственно распределенных неполных данных по окружающей среде

82. Структура и программирование ПЛИС фирмы Altera в САПР Quartus II, её применение в лабораторном стенде

83. Применение программного комплекса Electronics Workbench для разработки радиоэлектронных устройств

84. Применение двойных интегралов к задачам механики и геометрии

85. Использование численных методов для решения дифуpов (2-го порядка) (, демонстрация применения интерполяции в среде MATHCAD-а)

86. Шифросистемы с открытым ключом. Их возможности и применение.
87. ПРИМЕНЕНИЕ "ПУЛЬМОСАНА – 2" ПРИ ЛЕЧЕНИИ ТЕЛЯТ БОЛЬНЫХ БРОНХОПНЕВМОНИЕЙ ( ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА )
88. Применение электроники и биомеханики при протезировании

89. Дезинфицирующие препараты и их применение в хирургии

90. Применение ультразвука в медицине

91. Применение психологических знаний в процессе оперативно - розыскной деятельности

92. Применение милицией физической силы, спецсредств и огнестрельного оружия

93. Применение судами условного осуждения

94. Расчет информационной нагрузки программиста, оптимальное рабочее место с точки зрения эргономики, расчет вентиляции

95. Дидактические игры и их применение на уроках английского языка

96. Обучение младших школьников с применением компьютерной поддержки

Точилка механическая, металлический корпус.
Механическая точилка имеет прозрачный контейнер. Удобная и безопасная точилка оснащена механизмом, позволяющим крепить ее к столу. Нож из
1097 руб
Раздел: Точилки
Сушилка для белья напольная складная, 181х54х95 см, серая.
Сушилка для белья напольная складная. Размеры: 181x54x95 см. Цвет каркаса: серая. Размер в раскрытом виде: 181х95х54 см.
733 руб
Раздел: Сушилки напольные
8 цветных смывающихся фломастеров для малышей.
336 руб
Раздел: 7-12 цветов

97. Применение избирательных технологий на выборах в Пермскую городскую Думу 2000 года: технологичность выборов

98. Сегнетоэлектрики, их свойства и применение

99. Оптико-электронные приборы и их применение

100. Изучение экономической целесообразности применения ООО <Сибирь-связь> зарубежных технологических разработок по строительству офисных телекоммуникационных сетей на базе систем микросотовой связи стандарта DECT


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.