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

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

Задача остовных деревьев в k–связном графе

Коврик для запекания, силиконовый "Пекарь".
Коврик "Пекарь", сделанный из силикона, поможет Вам готовить вкусную и красивую выпечку. Благодаря материалу коврика, выпечка не
202 руб
Раздел: Коврики силиконовые для выпечки
Ночник-проектор "Звездное небо и планеты", фиолетовый.
Оригинальный светильник - ночник - проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фонариков) 2) Три
330 руб
Раздел: Ночники
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение

Министерство Науки и Образования Республики Молдова Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: «Задача остовных деревьев в k–связном графе»работу выполнил ст. V курса гр.52MI Жуков В. Работу приняла: Dr.физ–мат. наук Присэкару В.К. Кишинев–2002 Содержание:Введение .2 Глава I Основные определения .4 §1 Основные определения теории графов .4 §2 Матрицы смежности и инцидентности .10 §3 Деревья .13 Глава II Связность 18 §4 Вершинная связность и реберная вязность 18 §5 Двусвязные графы .22 §6 Теорема Менгера . .32 Глава III Выделение k непересекающихся остовных деревьев 2k–реберно связном графе 36 §7 Построение k непересекающихся остовных деревьев . . 37 §8 Необходимость условия 2k . .40 §9 Текст программы . . 42 Вывод .51 Введение Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач–проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов. Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять – двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии. Вследствие этого развития предмет теории графов является уже обширным, что все его основные направления невозможно изложить в одном томе. В настоящем первом томе предлагаемого двухтомного труда сделан акцепт на основные понятия и на результаты, вызывающие особый систематический интерес. По теории графов имеется очень мало книг; основной была книга Д. Кёнига (1936), которая для своего времени давала превосходнейшее введение в предмет. Довольно странно, что таких книг на английском языке до сих пор не было, несмотря на то, что многие важнейшие результаты были получены американскими и английскими авторами. Глава I Основные понятия §1 Определения. Предметом первых задач в теории графов были конфигурации, состоящие из точек и соединяющих их линий.

В этих рассмотрениях было несущественно, прямые ли это линии или же они являются криволинейными непрерывными дугами, соединяющими две концевые точки, где расположены эти линии, являются ли они длинными или короткими. Существенно только то, что они соединяют две данные точки. Это приводит к определению графа как абстрактного математического понятия. Рассматривая множество V, состоящее из соединенных некоторым образом точек. Назовем V множеством вершин и элементы vV–вершинами. Граф G=G(V) (1.1) c множеством вершин V есть некоторое семейство сочетаний, или пар вида E=(a, b), a,bV (1.2) указывающие, какие вершины являются соседними. В соответствии с геометрическим представлением графа каждая конкретная пара (1.2) называется ребром графа; вершины a и b называются концевыми точками, или концами ребра. Можно использовать и другой подход. Если даны два множества V1 и V2 то можно образовать множество всех пар (v1,v2), v1V2. Это множество пар называется произведением и обозначается через V1(V2. В нашем случае каждая пара вершин (a, b) есть элемент произведения V(V. Таким образом можно сказать, что граф G из (1.1) с данными ребрами (1.2) есть некоторое подмножество произведения V(V. Это определение графа должно быть дополнено в одном важном отношении. В определении ребра (1.2) можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок несуществен, т.е. если E=(a, b)=(b, a), то говорят, что Е есть неориентированное ребро; если же этот порядок существен, то Е называется ориентированным ребром. В последнем случае а называется также начальной вершиной, а b–конечной вершиной ребра Е. Можно также говорить, что Е есть ребро, выходящее из вершины а (отходящее от вершины а, исходящее из вершины а) и входящее в вершину b (подходящее к вершине b, заходящее в вершину b). Как в случае ориентированного, так и в случае неориентированного ребра говорят, что ребро Е из (1.2) инцидентно вершинам a и b, а также что а и b инцидентны Е. В приложениях граф обычно интерпретируется как сеть, в которой вершинами G являются узлы. Два узла a и b соединяются непрерывной кривой (в частности прямолинейны отрезком) тогда и только тогда, когда имеется пара (1.2). На рисунках узлы будут обозначаться маленькими кружками, а ориентация, если нужно, – стрелкой на представляющей ребро кривой (рис. 1.1). Граф называется неориентированным, если каждое его ребро не ориентированно, и ориентированным, если ориентированны все его ребра. На рис.1.2 приведены примеры неориентированных графов. На рис 1.3 изображены ориентированны графы. В ряде случаев естественно рассматривать смешанные графы, имеющие как ориентированные, так неориентированные ребра. Например, план города можно рассматривать как граф, в котором ребра представляют улицы, а вершины – перекрестки; при этом по одним улицам может допускаться лишь одностороннее движение, и тогда на соответствующих ребрах вводится ориентация; по другим улицам движение двустороннее, и на соответствующих ребрах уже никакой ориентации не вводится. Мы уже отмечали, что при фактическом изображении графа имеется большая свобода в размещении вершин и в выборе формы соединяющих их дуг.

Поэтому может оказаться, что один и тот же граф представляется совсем различными чертежами. Будем говорить, что два графа G и G' изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин V и V’, что вершины соединены ребрами в одном из графов в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то их направления также должны соответствовать друг другу. На рис 1.2 приведены примеры изоморфных графов, образованных ребрами и вершинами правильных многогранников. Вершина не инцидентна никакому ребру, называется изолированной. При определение множества вершин V данного графа часто имеет смысл учитывать только неизолированные вершины. Граф, состоящий только из изолированных вершин, называется нуль–графом и может быть обозначен через 0. другим важным случаем является (неориентированный) полный граф U=U(V), (1.3) ребрами которого являются всевозможные пары (1.2) для двух различных вершин a и b из V. На рис. 1.4 даны схемы полных графов для множеств вершин из четырех и из пяти элементов. В ориентированном полном графе U(d) имеются пары ребер, по одному в каждом направлении. Соединяющие любые две различные вершины a и b. Сформулированное выше определение графа, вместе с соответствующим изображением, достаточно для многих задач. Однако для некоторых целей желательно понятие графа несколько расширить. Во–первых, можно получить ребра, у которых обе концевые точки совпадают: L=(a, a). (1.4) Такое ребро (1.4) будет называться петлей. При изображении графа петля будет представляться замкнутой дугой, возвращающейся в вершину а и не проходящей через другие вершины (рис 1.5). Петля обычно считается неориентированной. Можно расширить полный граф U в (1.3) до полного графа с петлями U0, добавляя петлю в каждой вершине, так что ребрами U0 являются все пары (1.2), где допускается и a=b. Во–вторых, можно расширить понятие графа, допуская, чтобы пара вершин соединялась несколькими различными ребрами Ei=(a, b)i, (1.5) как это изображено на рис. 1.6. Для ориентированного графа две вершины a и b могут соединяться несколькими ребрами в каждом из направлений: Ei=(a, b)i, =(a, b)j, (рис. 1.7). Чтобы проиллюстрировать случай, для которого эти понятия оказываются естественными, рассмотрим какое–либо командное соревнование, например турнирную таблицу лиги бейсбола. Вершинами соответствующего графа являются команды. Пара команд А и В связывается ребром каждый раз, когда они сыграли. Если А выиграла у В, то это ребро будем ориентировать от А к В. а если В выиграла у А, то противоположном направлении; в случае ничьей ребро будет неориентированным. Для каждого графа G существует обратный граф G , получаемый изменением ориентации каждого из ребер G на противоположную. Для каждого ориентированного графа существует также соотнесенный неориентированный граф Gu, ребрами которого являются ребра G, но уже без ориентаций. Иногда удобно превратить неориентированный граф G в ориентированный граф Gd при помощи процесса удвоения, состоящего в замене каждого ребра G парой с теми же концами и приписывании им противоположных ориентаций.

У него есть своя доска, или планшет, или набор досок и планшетов, на которых он рисует разные схемы. У него есть определенные способности действовать, интериоризованные «овнутренные» средства, какие-то цели, задачи, перспективная линия, образование, происхождение, принадлежность к определенным группам. Он имеет определенное место, и это место особым образом связано с четырьмя другими ближайшими местами (схема 13). Правила работы с пустыми местами Двадцать два года назад я занимался исследованием детских учебных задач. Там была такая проблема. Есть прямые арифметические задачи: на дереве сидело пять птичек, прилетело шесть, сколько стало всего? Эти задачи дети решают легко и быстро. А косвенные задачки: на дереве сидели птички, прилетело еще шесть, стало одиннадцать, сколько было вначале?P дети почему-то решают с трудом. И вот методисты, педагоги, психологи все ломают голову. А оказалось, что все очень просто. Их учили так: если у тебя птички прилетали, надо складывать, а если улетали, то надо вычитать. Их так учат, а потом дают им косвенную задачку

1. Аллотропные видоизменения углерода: графит и алмаз

2. Граф А. А. Аракчеев. Современный взгляд на личность на основе анализа и сравнительной характеристики исторических источников и литературы

3. Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных

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

5. Огляд графічних редакторів

6. Дискретная математика: "Графы"
7. Поиск клик в графах
8. Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика»

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

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

11. Графы

12. Теория графов

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

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

15. Штеффи Граф

16. Альфьери Витторио, граф д’Асти

Фоторамка "Poster red" (30х40 см).
Рамка настенная может располагаться как вертикально, так и горизонтально. Для фотографий размером: 30х40 см. Материал: пластик.
342 руб
Раздел: Размер 30x40
Набор детской посуды "Авто", 3 предмета.
Набор посуды для детей включает в себя три предмета: суповую тарелку, обеденную тарелку и кружку. Набор упакован в красочную, подарочную
397 руб
Раздел: Наборы для кормления
Глянцевая бумага для струйных принтеров "Lomond", 50 листов, А4.
Глянцевые фотобумаги наилучшим образом передают яркие, насыщенные цвета с множеством оттенков и цветовых градаций. Покрытие бумаги:
378 руб
Раздел: Фотобумага для цветной печати

17. Книгоиздатель граф Н.П. Румянцев

18. Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала

19. AGraph: библиотека классов для работы с помеченными графами

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

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

22. Александр Дюма. Граф Монте-Кристо
23. «Мысль семейная»: роман графа Л.Н. Толстого «Анна Каренина»
24. «Война и мир»: главная книга графа Л.Н. Толстого

25. Типовой расчет графов

26. Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

27. Алгоритмы на графах. Независимые и доминирующие множества

28. Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

29. Види компютерної графіки

30. Вирізання картинок з екрану та запис їх в BMP форматі (для графіки) і TXT форматі (для тексту)

31. Комп’ютерна графіка

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

Электрогрелка "ГЭМР5-60".
Материал: высококачественный текстиль. Напряжение питания: 220 В. Потребляемая мощность 40 Вт. Переключатель режимов: есть
486 руб
Раздел: Грелки
Фляга S.Quire "Птицы" 0,24 л, сталь, серебристый цвет с рисунком.
Фляги S.Quire изготавливаются из высококачественной нержавеющей пищевой стали с применением современных методов производства и
760 руб
Раздел: Фляжки сувенирные
Тарелка Lubby "Веселые животные" с присоской.
Тарелка "Lubby" для кормления незаменима в период, когда Ваш малыш учится есть самостоятельно. Присоска препятствует свободному
345 руб
Раздел: Тарелки

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

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

35. Поліграфічний синтез кольорових зображень

36. Реалізація функцій бібліотеки графіки для виводу тексту у графічному режимі (OutTextXY, SetTextStyle)

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

38. Дослідження графіку функції y=cos(x)*ln(x)
39. Графічна бібліотека OpenGl
40. Графічне та геометричне моделювання та інтерактивні системи» На тему «Система бухгалтерського обліку»

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

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

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

44. Застосування поліграфічної продукції у політичній рекламі

45. Графы

46. Графы. Основные понятия

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

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

Смываемые фломастеры "Супер чисто" с толстым наконечником, 8 штук.
В картонной коробке 8 разноцветных фломастеров. Они выполнены из качественных экологически чистых материалов. Созданные на основе
393 руб
Раздел: 7-12 цветов
Пломба свинцовая 10 мм, упаковка 1 кг.
Рекомендуется использовать совместно с витой проволокой или шпагатом. Устанавливается с помощью пломбиратора. Применение свинцовых пломб
362 руб
Раздел: Прочее
Карандаши цветные BIC "Kids ECOlutions Evolution", пластиковые, 24 цвета.
Цветные заточенные карандаши «Evolution Kids», специально для маленьких детей. Грифели не ломаются при падении. Удобное, легкое
503 руб
Раздел: 13-24 цвета

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

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

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

52. Формування графічних умінь молодших школярів на уроках трудового навчання

53. Напівтони та колір у поліграфії

54. Метод графо-аналитических зависимостей в налоговом менеджменте
55. Структура графа состояний клеточных автоматов определённого типа
56. Есть ли жизнь во вселенной

57. Одиноки ли мы во Вселенной?

58. Одиноки ли мы во Вселенной?

59. Проблемы добычи алмазов в Якутии

60. Алмаз. Легенды и действительность

61. Алмазы

62. Роль Великой Октябрьской революции для России и мира. Была ли альтернатива февральской революции

63. Может ли Интернет нанести вред демократии?

64. Статья: "пойду ли я на дискотеку"

Канистра-бочонок со сливом, 20 л.
Изготовлена из пищевого полиэтилена. Пригодна для хранения питьевой воды. Имеет герметичную крышку, позволяющую полностью избежать
443 руб
Раздел: Баки, канистры
Настольная игра "Эволюция".
Разнообразие живых организмов, населяющих нашу планету, поистине поражает. Теория эволюции объясняет это различием способов, которые
1090 руб
Раздел: Карточные игры
Доска магнитная для рисования, со штампиками.
Магнитная доска предназначена для рисования; у доски стирающееся поле для создания рисунков при помощи специального маркера. На
347 руб
Раздел: Магнитные доски

65. Можно ли утверждать, что литература сегодня воспитывает читателя?

66. Идеальное общество, возможно ли оно (по роману Зацепина "Мы")

67. Возможна ли единая европейская или мировая цивилизация ?

68. Были ли в Германии плавающие танки накануне Второй Мировой Войны?

69. Мировые ресурсы, добыча алмазов и драгоценных металлов

70. Иллюзии восприятия, или всегда ли мы видим то, что видим
71. Соционика: можно ли прогнозировать отношения?
72. Исчезнет ли человек как вид?

73. Можно ли избежать столкновение цивилизаций?

74. Алмазы

75. Играют ли деньги главенствующую роль в современной экономике России

76. Протекционизм и фритредерство: следует ли искать "золотую середину"?

77. Существовала ли высокоразвитая цивилизация на Земле?

78. Умер ли марксизм?

79. Знает ли левая рука, что творит правая

80. Готовил ли Сталин нападение на Германию?

Коробка для хранения обуви, 610x340x130 мм.
Материал: полипропилен. Размер: 610x340x130 мм.
550 руб
Раздел: Короба, чехлы для обуви
Перчатки виниловые одноразовые, размер M, 100 штук.
Виниловые одноразовые перчатки применяются во время разных видов работ: в пищевой сфере, косметологии, при уборке. Перчатки мягкие и
305 руб
Раздел: Перчатки
Трусики Merries Юниор, 12-22 кг, экономичная упаковка, 38 штук.
Изготовлены из чистого хлопка, гладкого как шёлк и очень мягкого на ощупь, удобны в период обучения малыша к горшку; надеваются и
1448 руб
Раздел: Обычные

81. От Хрущева до Горбачева: был ли неизбежен развал СССР

82. Была ли связь между торжеством Франции в Крымской войне и ее разгромом под Седаном?

83. Было ли нападение Германии на СССР неожиданным

84. Наступит ли конец эпохи огнестрельного оружия?

85. Рекурсия

86. Джемс. Существует ли сознание
87. А была ли античная литература?
88. Согласны ли вы с А. С. Пушкиным в том, что “России определено было высшее назначение”?

89. Образ Иисуса в повести Л.Н. Андреева «Иуда Искариот», или Смеялся ли Христос?

90. Можно ли охарактеризовать поэзию С. А. Есенина как лирическую исповедь, биографию в стихах?

91. Нужны ли Обломовы России?

92. «Народ освобожден, но счастлив ли народ?»

93. Хорош ли русский язык?

94. Легко ли жить в 15 лет?

95. Современна ли сатира Маяковского

96. "Светлее алмазов горят в небе звёзды" (Английская литературная сказка как явление)

Багетная рама "Sandra" (серебряный), 40х50 см.
Багетные рамы предназначены для оформления картин, вышивок и фотографий. Оформленное изделие всегда становится более выразительным и
791 руб
Раздел: Размер 40x50
Стол детский Little Angel "Я расту" (цвет: салатовый).
Размер стола: 56х56х50 см. Материал: пластик. Цвет: салатовый.
1476 руб
Раздел: Столики
Ванная комната "Конфетти".
Набор мебели для кукольной комнаты подойдет для кукол размером до 30 см. Комплектность: коврик большой, коврик, флакон - 2 штуки, пробка к
878 руб
Раздел: Ванные комнаты

97. Был ли выход у Катерины Кабановой?

98. Нужно ли передавать функции маркетинга на аутсорсинг?

99. Надо ли искать Хиггс – Бозон и кварки?


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