телефон 978-63-62
978 63 62
zadachi.org.ru рефераты курсовые дипломы контрольные сочинения доклады
zadachi.org.ru
Сочинения Доклады Контрольные
Рефераты Курсовые Дипломы
путь к просветлению

РАСПРОДАЖАТовары для спорта, туризма и активного отдыха -30% Образование, учебная литература -30% Канцтовары -30%

все разделыраздел:Компьютеры, Программирование

Гамильтоновы графы и сложность отыскания гамильтоновых циклов

найти похожие
найти еще

Ночник-проектор "Звездное небо, планеты", черный.
Оригинальный светильник-ночник-проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фанариков); 2) Три
350 руб
Раздел: Ночники
Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10
Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее
Федеральное агентство по образованию РФ САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО Кафедра геометрииГамильтоновы графы и сложность отыскания гамильтоновых циклов КУРСОВАЯ РАБОТАНаучный руководитель Старший преподаватель должн., уч. степень, уч. зван. подпись, дата инициалы, фамилияСаратов 2010 СодержаниеВведение Гамильтоновы графы 1.1 Основные определения и результаты 1.2 Теоремы достаточности гамильтонова графа Методы отыскания гамильтоновых циклов 2.1 Алгебраические методы 2.2 Метод перебора Робертса и Флореса 2.2.1 Улучшение метода Робертса и Флореса Приложение Заключение Список литературы ВведениеЦелью моей курсовой работы является: Ознакомление с основными понятиями, связанными с гамильтоновыми графами и циклами. Рассмотреть задачи и методы отыскания гамильтоновых циклов в графах 3. Создание программы для нахождения гамильтоновых циклов. Прежде всего, чтобы внести ясность и уточнить терминологию, хотелось бы дать определения некоторым элементам графа таким, как маршрут, цепь, цикл. Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: , , , в которой любые два соседних элемента инцидентны. Если = , то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, ребра) различны, то маршрут называется простой цепью. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром. 1. Гамильтоновы графы 1.1 Основные определения и результаты Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира. Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным. Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе. Замечание. Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1, , vp графа G добавить вершины u1, , up и множество ребер {(vi, ui)} {(ui, vi 1)}. Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) — по входящим. В отличии от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет.

Молочный гриб необходим в каждом доме как источник здоровья и красоты
Молочный гриб необходим в каждом доме как источник здоровья и красоты + книга в подарок

 От 'Ильи Муромца' до ракетоносца - Краткий очерк истории Дальней Авиации

Действия ночью отличались от дневных и имели ряд особенностей. Прежде всего, темная ночь снижала эффективность огня зенитной артиллерии и истребителей. Это создавало условия для широкого применения устаревших типов бомбардировщиков. При действиях ночью учитывалась продолжительность темного времени, освещение луны, степень видимости аэродрома и состояние погоды, а также сложность отыскания, подсвета, поджога и эффективного поражения самолетов на аэродроме. Этими трудностями и особенностями определялись и способы действий. Основное тактический прием заключался в самостоятельных действиях экипажей на разных высотах, с небольшим временным интервалом. Для повышения эффективности, увеличения времени воздействия на противника экипажи совершали по 3-5 и более заходов на цель, находясь над ней до 10-15 минут. При сильном противодействии артиллерии они подходили к цели с таким расчетом, чтобы в районе ее одновременно находились 3-4 самолета, что рассредоточивало зенитный огонь. Высота удара колебалась от 1000 до 2000 м, а при отсутствии огня артиллерии снижалась до 400 - , 500 м, что позволяло вести пулеметный огонь

скачать реферат Метод Zero Knowledge Proofs

Метод ZKP может использоваться не только для примера с графами но и на многих других примерах, просто в данном случае легче всего объяснить в чем суть метода ZKP. Хоть и явны видны преимущества данного вида кодировки нельзя забывать и про систему (PASSWORD)овых шифровок так как если охраняется не очень важный объект то проще и быстрее проверять (PASSWORD) чем проводить проверку методом ZKP. Мы попробовали пройти систему кодировки ZKP. Для примера мы разобрали разные фрагменты графов что бы найти закономерность в построении гамильтонова цикла .Мы можем найти алгоритм построения гамильтонова цикла на данных фрагментах, что бы в дальнейшем строить этот цикл на более сложных графах. Пример1. A A E D C B F S P G A В данном графе легко можно B построить гамильтонов цикл F G E так как в данном графе есть два S P контура , которые находятся друг в друге и соединены точками. C D Таким образом построение данного графа является самим гамильтоновым циклом и практически все графы строятся на основе самого гамильтонова цикла. С добавлением других ребер.

Спиннер трехлучевой "Цветомузыка", с bluetooth (зеленый).
Компактная стильная игрушка для взрослых и детей, предназначенная для вращения на пальцах. Состоит из подшипников, благодаря которым
465 руб
Раздел: Спиннеры
Одеяло лен + хлопок, 140х205 см.
Облегченное стеганое одеяло с льняным наполнителем подарит вам прохладу в жару и тепло в холод. Льняное волокно обладает уникальными
1389 руб
Раздел: Одеяла
Стиральный порошок "PoshOne Ecobaby Delicate" для детской одежды и деликатных тканей 2,5кг.
Posh one 2500 gr (коробка с мерной ложкой 30 гр): сухой стиральный концентрированный порошок для: цветного белья. Оригинальные импортные
684 руб
Раздел: Стиральные порошки
 Целостный метод - теория и практика

К задаче коммивояжера в формальном виде сводятся многие задачи управления, экономики, планирования и организации. Решить ЗОК простым перебором для больших n практически невозможно, так как число возможных решений равно (n-1)! или «(n-1) факториал». Применение принципа обогащения к решению ЗОК позволяет построить эффективную технологию. В этом случае технология решения состоит из двух основных алгоритмов. Первый алгоритм позволяет обогатить исходный массив данных, исключая из него те «расстояния», которые не могут участвовать в оптимальном маршруте. Второй алгоритм позволяет найти оптимальный (или близкий к оптимальному) маршрут коммивояжера. Задача поставлена и решена, как известная задача теории графов о нахождении оптимального гамильтонова цикла в графе[92] . Для оптимального гамильтонова цикла справедливо следующее условие оптимальности: для любого простого маршрута, являющегося участком оптимального гамильтонова цикла и проходящего вершины графа в последовательности i1, i2, i3, ...,ia, (a=4,5, ...,n; il=1,2, ..., n) сумма весов входящих в него ребер ? (i1i2i3 ..., ia) является минимальной в сравнении с любой другой суммой вида ? (i1i?2i?3...i?a-1ia): ? ( i1i2i3...ia) = min ? (i1i?2i?3...i?a-1ia)               (1) при a =4, 5, ..., n; i=1,2, ..., n; i?2, i?3,..., i?a-1, ?P. Здесь i?2, i?3,..., i?a-1 — одна из перестановок чисел i2, i3, ..., ia-1, P — множество всех перестановок этих чисел

скачать реферат Теория графов

На изображенном графе все 5 простых циклов четные.(РИСУНОК 3.1) Суть теоремы в том, что на этом графе невозможно найти цикл (как простой, так и непростой) нечетной длины, то есть содержащий нечетное число ребер. Теорема 3.6. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень. Теорема 3.7. Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа. Доказательство этой теоремы очень интересно и характерно для теории графов. Его также следует считать конструктивным (обратите внимание на то, как •использована при этом теорема 3.6). Для доказательства к исходному графу присоединяем ребро (А, В); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в нем можно проложить эйлеров цикл ?. И если теперь в этом цикле удалить ребро (А, В), то останется искомая цепь АВ. ( На этом любопытном приеме основано доказательство следующей теоремы, которую следует считать обобщением теоремы 3.7. Теорема 3.8. Если данный граф является связным и имеет 2k вершин нечетной степени, то в нем можно провести k различных цепей, содержащих все его ребра в совокупности ровно по одному разу. Теорема 3.9. Различных деревьев с перенумерованными вершинами можно построить -2.

 Целостный метод системной технологии и системная экология

Для оптимального гамильтонова цикла справедливо следующее условие оптимальности: для любого простого маршрута, являющегося участком оптимального гамильтонова цикла и проходящего вершины графа в последовательности i1, i2, i3, ...,ia, (a=4,5, ...,n; il=1,2, ..., n) сумма весов входящих в него ребер ? (i1i2i3 ..., ia ) является минимальной в сравнении с любой другой суммой вида ? (i1i?2i?3...i?a-1ia): ? ( i1i2i3...ia) = min ? (i1i?2i?3...i?a-1ia ) (1) при a =4, 5, ..., n; i=1,2, ..., n; i?2, i?3,..., i?a-1, ?P. Здесь i?2, i?3,..., i?a-1 — одна из перестановок чисел i2, i3, ..., ia-1, P — множество всех перестановок этих чисел. Очевидно, что если это условие не выполняется для каких-либо значений a и i, то существует гамильтонов цикл с меньшей длиной пути обхода вершин i1, i2, i3, ..., ia-1,ia . Но, если полученный гамильтонов цикл оптимален, то его нельзя улучшить изменением пути обхода вершин i1, i2, i3, ..., ia для любого a, имеющего значения в пределах от 4-х до n. Значения a не могут быть меньше четырех, так как очевидно, что никакие два гамильтонова цикла не могут отличаться менее, чем тремя ребрами, проходящими четыре вершины поcледовательно в одном из двух возможных вариантов обхода: i1,i2,i3,i4 или i1,i3,i2,i4

скачать реферат Особенности кинетики реакций на поверхности гетерогенных катализаторов

Уравнение (47) эквивалентно уравнению (48) теории маршрутов ,(48) где Р – число линейно независимых маршрутов (базис маршрутов), S – число стадий и I – число линейно независимых интермедиатов (ранг матрицы ). В случае планарных графов число простых циклов равно числу граней КГ (2 грани на КГ1). Рассмотрим алгоритмы вывода кинетических уравнений для линейных механизмов на основании методов теории графов. Введем несколько определений. Циклом графа называют любую последовательность ориентированных дуг (стадий), начинающуюся и заканчивающуюся в одной и той же вершине. Цикл КГ соответствует циклическому превращению интермедиатов. Величина цикла С (вес цикла) выражается произведением весов соответствующих дуг (весов элементарных реакций) Напомним, что вес стадии равен скорости j-той стадии в одном направлении, деленной на концентрацию i-того интермедиата, участвующего в j-той стадии: Если = 1, то . Для КГ1 (и, соответственно, КГ2) величины циклов (веса циклов), включающих стадии 1, 2 и 1, 3, Направление циклов на КГ выбирается в соответствии с направлением маршрутов, которое в свою очередь определяется направлением стадий и вектором стехиометрических чисел.

скачать реферат Графы

На рисунке 2 приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям. Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками. Не трудно понять, что граф – дерево всегда можно изобразить так, чтобы его ребра не пересекались. Тем же свойством обладают графы, образованные вершинами и ребрами выпуклых многогранников. На рисунке 3 приведены графы, соответствующие пяти правильным многогранникам. В графе соответствующем тетраэдру, все четыре вершины попарно соединены ребрами.   Рассмотрим граф с пятью вершинами, попарно соединенными друг с другом (рис. 4). Здесь ребра графа пересекаются. Невозможно его изобразить так, чтобы пересечений не было, как невозможно выполнить намерения трех человек, описанных Льюсом Кэрроллом. Они жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке 5.

скачать реферат Цикл производственного менеджмента

В этом случае нередко сохраняются старые и избыточные мощности. Более подробно о производственных мощностях сказано в разделе, посвященном производственной программе. Масштаб и ориентация производства. Решения о масштабе и ориентации производства увязаны с решениями о производственных мощностях и включают вопросы: размер предприятия; место расположения; что будет производиться. Например, во многих странах с рыночной экономикой большое значение придают небольшим предприятиям, расположенным в непосредственной близости от рынка. Такие предприятия широко распространены в Японии. Ориентация производства связана с его специализаций (однородная или разнородная продукция). От этого зависят число различных производственных процессов, степень их сложности. Следующими стадиями цикла производственного менеджмента является определение условий, организация, исполнение. 2. Определение условий, организация, исполнение После разработки плана начинается следующая фаза производственного менеджмента. Необходимо оценить условия выполнения плана и приступить к организации его выполнения. Прежде всего, нужно оценить внешние и внутренние факторы, которые могут оказать влияние на реализацию плана.

скачать реферат Основы маркетинга

Различают виды сервиса: 1. предпродажный (инструкция). 2. сервис при продажи (доставка, демонстрирование). 3. после продажный сервис. Формы осуществления сервиса. 1. сервис осуществляется исключительно персоналом производителя. 2. сервис осуществляется производителями через собственные сервисные центры. 3. сервис осуществляется независимыми организациями, с которыми производитель заключает договора на оказания сервисных услуг. 4. обеспечивается тем звеном распределения, который находится ближе всего к потребителю, а производитель поставляет только запасные части. 7. ЖИЗНЕННЫЙ ЦИКЛ ТОВАРАЖизненный цикл товара – это процесс развития продаж и получения прибыли во времени. Если товар рассматривать в динамике можно получить граф. изображение традиционного жизненного цикла с отчетливым выделением пяти этапов, определяющих две важные проблемы: 1. как эфиктивно работать с товарами находящихся на рынке, чтобы продлить срок их жизни.2. когда начинать обновления продукции для замены устаревающих товаров. Нулевая стадия – разработка товара, превращения замысла товара в реальное изделие. Для этого этапа характерны большие материальные и физические затраты, прибыль отсутствует.

Этажерка "Люкс-5" с сидением, 3-х ярусная.
Удобная, компактная и функциональная этажерка для обуви с ящиком «Люкс 5» выполнена из металлических трубок с антикоррозионным
1624 руб
Раздел: Полки напольные, стеллажи
Ракета "Мир".
Модель 2018 года. Боковые разгонные блоки отделяются одновременно при перемещении оранжевого кольца вверх, следующая ступень также
412 руб
Раздел: Космический транспорт
Пакеты фасовочные, 10(+8)x27 см (1000 штук).
Область применения: расфасовка, упаковка продуктов питания и товаров народного потребления как на производстве, так и в быту. Размер:
306 руб
Раздел: Пакеты для продуктов
скачать реферат Задача коммивояжера

В этот период активизировался интерес к классическим комбинаторным задачам.  Классические комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок. В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами. Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений – задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем. Задача коммивояжера. Общее описание Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики.

скачать реферат Лекции по вычислительной математике

Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о ком-мивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер при-писать вес Ґ, считая, что Ґ - это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь лег-чайший гамильтонов цикл, то при наличии у него ребер с весом Ґ можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший га-мильтонов цикл окажется конечным по весу, то он и будет иско-мым циклом в исходном графе. Отсюла следует, что задачу о коммивояжере достаточно ре-шить для полных орграфов с весовой функцией. Сформулируем теперь это в окончательном виде: пусть - полный ориентированный граф и - весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

скачать реферат Программа Mathematics

В новой версии оно пополнилось пакетами для решения некоторых типов алгебраических неравенств и симметричных полиномов и, кроме того, добавлена Гамильтонова алгебра кватернионов и элементы полей Пигуа. Вычисления Это дополнение содержит пакеты, позволяющие рас­ширять возможности программы при вычислении интег­ралов, нахождении прсделов, решении дифференциальных уравнений и задач линейной алгебры в различных системах координат, а также включает команды преобразования Фу­рье и Лапласа, обобщенные функции, вариационные мето­ды. В новой версии оно пополнилось пакетом для нахождения полных интегралов и дифференциальных инвариантов нелинейных уравнений в частных производных. Дискретная математика Дополнение предлагает примерно 200 функций для проведения исследований в области комбинаторики и те­ории графов; вычислительную геометрию, которая со­держит несколько геометрических функций для непараметрического анализа данных; пакеты для оперирования с функциями от целых чисел, в частности для решения рекуррентных уравнений, выполнения преобразований.

скачать реферат Криптографические протоколы

Труднорешаемые задачи, способ сведения одной задачи к другой, а также случайные числа должны по возможности выбираться так, чтобы у Бориса не появилось никакой информации относительно решения исходной задачи даже после многократного выполнения шагов протокола. Не все труднорешаемые задачи могут быть использованы при доказательстве с нулевым разглашением конфиденциальной информации, однако большинство из них вполне пригодны для таких целей. Примерами могут служить отыскание в связном графе цикла Гамильтона (замкнутого пути, проходящего через все вершины графа только один раз) и определение изоморфизма графов (два графа изоморфны, если они отличаются только названиями своих вершин). Параллельные доказательства с нулевым разглашением конфиденциальной информации Обычный протокол доказательства с нулевым разглашением конфиденциальной информации требует, чтобы Антон и Борис последовательно повторили его шаги раз. Можно попробовать выполнять действия, предусмотренные этим протоколом, одновременно: 1. Антон использует имеющуюся у него информацию и сгенерированных случайных чисел, чтобы свести труднорешаемую задачу к другим труднорешаемым задачам, изоморфным исходной задаче.

скачать реферат Вклад ученого в теорию связи

Его заслуги были отмечены всевозможными премиями и наградами, в том числе международными премиями Бальцана, Вольфа. За цикл работ по теории случайных процессов А. Н. Колмогоров  и А. Я. Хинчин были удостоены Государственной премии СССР, за труды по теории возмущений гамильтоновых систем (совместно с академиком  В. И. Арнольдом) – Ленинской премии. Двенадцать учеников крупнейшего ученого ХХ столетия А. Н. Колмогорова стали членами Академии наук СССР. Научную школу Колмогорова можно поставить в один ряд со школами великих физиков Резерфорда и Бора. Умер Андрей Николаевич 20 октября 1987 года. Список литературы

Самоклеящиеся этикетки, A4, 105x74 мм, 8 этикеток на листе.
Формат: А4. Размер: 105x74 мм. В комплекте: 100 листов (на 1 листе 8 этикеток).
500 руб
Раздел: Бейджи, держатели, этикетки
Защита от включения конфорок плиты, 4 штуки, прозрачный.
Защита на колпачки газовой плиты. Рукоятки не должны превышать 50 мм в диаметре, а расстояние между ними не меньше 67 мм.
605 руб
Раздел: Безопасность ребенка
Горка детская малая, арт. 11050.
Горка детская малая состоит из лесенки и желоба для скатывания. Горка очень устойчивая, изготовлена из яркого, прочного, нетоксичного
2067 руб
Раздел: Горки
скачать реферат Алгоритм удаления циклов в графе вертикальных ограничений задачи трассировки многослойного канала

В этом случае проходящий через вершину цикл не может быть удален путем расщепления только данной вершины. Использование локального графа контактов позволяет свести задачу разбиения контактов на группы к задаче раскраски неориентированного графа. Необходимо раскрасить локальный граф контактов в минимальное число цветов так, чтобы вершины, соединенные ребром, оказались раскрашены в разные цвета. Раскраска графа в минимальное число цветов будет соответствовать разбиению сегмента на минимальное число частей, достаточное для удаления циклов в VCG. Необходимо отметить, что, несмотря на сложность задачи раскраски произвольного графа в минимальное число цветов, для данного случая задача всегда может быть решена методом полного перебора, так как размерность локального графа контактов определяется числом контактов в цепи и для сигнальных цепей обычно не превышает 5. Если локальный граф контактов не содержит нечетных циклов, то, по теореме Кенига , он может быть раскрашен в два цвета. В этом случае достаточно бинарного доглега. В остальных случаях требуется мульти-доглег.

скачать реферат Методы и алгоритмы компоновки, размещения и трассировки печатных плат

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

скачать реферат Проблема истории в художественном мире А.С.Пушкина

Циклы относятся друг к другу также, во всяком случае, аналогично тому, как пятью годами ранее в Михайловском трагическому “Борису Годунову” противостоял анекдотический “Граф Нулин”, рожденный “мыслью пародировать историю и Шекспира” / “Заметки о “Графе Нулине””, 1830/. “Медный всадник” – поэма философско – историческая, лиро-эпическая, отразившая всю сложность и глубину раздумий Пушкина над историей. Вместе с тем поэма носит обобщенно-символический характер, ее образы и картины получают метафизическое, символическое истолкование. Сам образ Медного всадника – это реально существующий памятник Петру, Фальконе, но в поэме Пушкина эта статуя наделяется чертами живого существа. Лицо всадника возгорается гневом, “какая дума на челе”, он скачет за Евгением, становится символом государства, основанного Петром. Символична картина наводнения, разгула природной стихии. В “Медном всаднике” прямо упоминаются три царствования. Они и есть три узловые эпохально-временные точки поэтического действия, три культурно-исторических слоя: Эпоха Петра и строительства Петербурга: На берегу пустынных волн Стоял он дум великих полн, И вдаль глядел.

скачать реферат Типовой расчет графов

Данная работа является типовым расчетом 2 по курсу "Дискретная математика" по теме "Графы", предлагаемая студентам МГТУ им. Баумана. (Вариант 17). Сразу хочу сказать для своих коллег: Граждане! Имейте терпение и совесть, поймите, что я это делаю для Вас с целью помочь разобраться в этой теме, а не просто свалить очередной предмет. Мне известно, как непросто сейчас с литературой, и с информацией вообще. Поиски неизвестно какой книги занимают много времени, поэтому в конце я привел небольшой список литературы, составленный мной из различных источников в дополнение к списку, написанному ранее в работе по графам (о постановке лаб. работ по алгоритму Прима и Дейкстра), которая, я надеюсь, есть в сети. Содержание работы: Типовой расчет состоит из 11-ти задач: 1, 2 и 3 задачи относятся к способам задания графов и опредению их характеристик, таких как диаметр, радиус и т.д. 4 и 5 задачи соответственно на алгоритм Прима и Дейкстра. Здесь я снова отсылаю Вас к более ранней работе (см. выше). 6-я задача о поиске максим ального потока в сети (метод Форда-Фалкерсона). 7-я задача - Эйлерова цепь (задача о почтальоне). 8-я задача - Гамильтонова цепь. 9-я задача - метод ветвей и границ применительно к задаче о коммивояжере. 10-я задача - задача о назначениях; венгерский алгоритм. 11-я задача - тоже методом ветвей и границ. Gор(V,X) Рис. 1 Задача1 Для неориентированного графа G, ассоциированного с графом Gор выписать (перенумеровав вершины) : а) множество вершин V и множество ребер X, G(V,X); б) списки смежности; в) матрицу инцидентности; г) матрицу весов. д) Для графа Gор выписать матрицу смежности.

телефон 978-63-62978 63 62

Сайт zadachi.org.ru это сборник рефератов предназначен для студентов учебных заведений и школьников.