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

РАСПРОДАЖАОдежда и обувь -30% Товары для дачи, сада и огорода -30% Товары для животных -30%

все разделыраздел:Математика

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

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

Забавная пачка денег "100 долларов".
Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь внимательней, и Вы увидите
60 руб
Раздел: Прочее
Совок большой.
Длина 21,5 см. Расцветка в ассортименте, без возможности выбора.
21 руб
Раздел: Совки
Мыло металлическое "Ликвидатор".
Мыло для рук «Ликвидатор» уничтожает стойкие и трудно выводимые запахи за счёт особой реакции металла с вызывающими их элементами.
197 руб
Раздел: Ванная
Министерство Науки и Образования Республики Молдова Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: «Задача остовных деревьев в 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 Определения. Предметом первых задач в теории графов были конфигурации, состоящие из точек и соединяющих их линий. В этих рассмотрениях было несущественно, прямые ли это линии или же они являются криволинейными непрерывными дугами, соединяющими две концевые точки, где расположены эти линии, являются ли они длинными или короткими.

Прежде чем ввести понятия вершинной и реберной связности, рассмотрим одну математическую модель, возникающую, в частности, при проектировании и анализе сетей ЭВМ. Имеется сеть, состоящая из центров хранения и переработки информации. Некоторые пары центров соединены каналами. Обмен информацией между любыми двумя центрами осуществляется либо непосредственно по соединяющему их каналу, если он есть, либо через другие каналы и центры. Сеть считается исправной, если каждая пара центров в состоянии обмениваться информацией. Такой сети естественно сопоставить граф: вершины–центры, ребра–каналы сети. Тогда исправной сети будет соответствовать связный граф. Важным понятием является надёжность (живучесть) сети, под которой обычно подразумевают способность сети функционировать при выходе из строя одного или нескольких центров или (и) каналов. Ясно, что менее надежной следует считать ту сеть, исправность которой нарушается при повреждении меньшего количества элементов. Оказывается, надежность сети можно измерять на основе вводимых ниже определений. Числом вершин связности (или просто числом связности) (G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. Так, например, (C )=2. Это вполне согласуется с интуитивным представлением том, что при >3 граф K сильнее связен, чем C . Граф G, представленный на рис. 4.1 связен, но его связность можно нарушить, удалив вершину 4. Поэтому (G)=1. Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее трех ребер. Например, G распадается на две компоненты при удалении ребер {4,5}, {4,6}, {4,7}. Чтобы учесть это обстоятельство, введем еще одно определение. Пусть G–граф порядка >1. Числом реберной связности (G) графа G назовем наименьшее число ребер, удаление которых приводит к несвязному графу. Число реберной связности графа будем считать равным нулю, если этот граф одновершинный. В качестве иллюстрации снова обратимся к графу G на рис. 4.1 Здесь (G). Ниже будет показано, что противоположное неравенство невозможно ни для какого графа. Определим некоторые элементы графа, играющие особую роль в дальнейших рассмотрениях. Вершина v графа G называется точкой сочленения (или разделяющей вершиной), если граф G – v имеет больше компонент, чем G. В частности, если G связен и v – точка сочленения, то G– v не связен. Аналогично ребро графа называется мостом, если его удаление увеличивает число компонент. Таким образом, точки сочленения и мосты – это своего рода «узкие места» графа. Граф, изображенный на рис. 4.2, имеет три точки сочленения a, b, c и один мост ab. Понятно, что концевая вершина моста является точкой сочленения, если в графе есть другие ребра, инцидентные этой вершине. Возвращаясь к рассматриваемой в начале параграфа сети, нетрудно заметить, что число вершинной связности и число реберной связности ее графа отражают чувствительность сети к разрушению центров и каналов соответственно, а мостам и точкам сочленения отвечают наиболее уязвимые места сети. Если (G) – минимальная степень вершин графа G, то очевидно, что (G), поскольку удаление всех ребер, инцидентных данной вершине, приводит к увеличению числа компонент графа. Выясним теперь соотношения между числами (G).

Таким образом, мы получили конечную или бесконечную матрицу смежности (вершин) М(G), которая полностью описывает G, если имеет однократные ребра. Обычно обозначения выбираются так, чтобы элементы (а, а), соответствующие петлям, располагались на главной диагонали матрицы М. Если G–неориентированный граф, то ребра (a, b) и (b, a) существуют одновременно, таким образом, неориентированным графам соответствуют симметрические матрицы смежности. Если G имеет кратные ребра, то числа 0 и 1 в клетках (a, b) можно заменить кратностями ((a, b) ребер, соединяющих а и b. Это дает описание графа G матрицей с целыми неориентированными элементами. Обратно, любая такая матрица может быть интерпретирована как граф, так что любые результаты для графов могут быть сформулированы как свойства таких матриц. Сказанное приводит к дальнейшему расширению понятия графа, использующему уже все конечные или бесконечные матрицы, элементами которых являются вещественные неотрицательные числа. Такие матрицы встречаются в различных областях математики. Например, стохастические матрицы – в теории вероятностей и в теоретической физике. Где рассматриваемая система имеет некоторое множество V возможных состояний, и любая пара состояний (a , b) связывается некоторой вероятностью перехода ((a, b). Другим примером является граф, представляющий схему дорог, в котором ((a, b) означает соответствующее расстояние между а и b. Графы могут быть также описаны матрицами другого вида. Всякий граф состоит из объектов двух типов–вершин и ребер. Можно построить матицу M1(G), строки которой соответствуют вершинам, а столбцы–ребрам. На месте (а, Е) в этой матрице поместим значение (=1, если а–начальная вершина ребра Е, значение (=-1, если а–конечная вершина, и (=0, если а не инцидентно Е. Если G–неориентированный граф, то можно использовать только значения (=1 и (=0. Эта матрица M1(G) называется матрицей инцидентности графа G. Введем, наконец, матрицу смежности ребер I(G), в которой и строки и столбцы отвечают ребрам G. Для простоты предположим. Что G не имеет петель, а ребра неориентированные и однократные. На месте (E, E’) в I(G) поместим (=1, если Е и Е’–различные ребра с общим концом, и (=0, если Е=Е’ или если они не имеют общего конца. Таким образом, I(G)–квадратная матрица, определяемая графом G. Можно встать и на другую точку зрения и рассматривать I(G) как матрицу смежности вершин для нового графа, также обозначаемого через I(G), вершинами которого являются ребра Е графа G, а ребрами–пары (E, E’) с (=1. Назовем I(G) графом смежности ребер или смежности графом для G. Существование такого графа, в котором бывшие ребра становятся вершинами и наоборот, объясняет двойственность между вершинами и ребрами, встречающуюся в некоторых вопросах теории графов. Фактическое построение смежности графа I(G) по чертежу графа G просто. На каждом ребре Е выбираем фиксированную точку еЕ, например середину Е. Пару таких вершин (е, е’) соединяем новым ребром, принадлежащим I(G), тогда и только тогда, когда соответствующие ребра Е и Е’ имеют общую вершину в G. Рис. 2.2 дает это построение для графа тетраэдра; смежностным графом для него является граф октаэдра.

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

 Большая Советская Энциклопедия (ГР)

Одни из них группируются в отдельные направления, другие стоят более изолированно. Среди сложившихся разделов Г. т. следует отметить задачи, относящиеся к анализу графов, определению различных характеристик их строения, например выяснение связности графа: можно ли из любой вершины попасть в любую; подсчёт графов или их частей, обладающих заданными свойствами, например подсчёт количества деревьев с заданным числом рёбер (дерево — неориентированный граф без циклов); решение транспортных задач, связанных с перевозками грузов по сети. Решен ряд задач по синтезу графов с заданными свойствами, например построение графа с заданными степенями вершин (степень вершины — число выходящих из неё рёбер). Имеет прикладное и теоретическое значение задача о выяснении возможности расположения графа на плоскости без самопересечений его рёбер (т. е. является ли данный граф плоским), задача о разбиении графа на минимальное число плоских графов. Для некоторых задач Г. т. (выше были приведены далеко не все) были разработаны методы их решения

скачать реферат Правила выполнения курсовой работы по дисциплине "Менеджмент"

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

Вешалка для одежды напольная, раздвижная ТД-00017.
Длина: 145 см. Регулируемая высота: 90-155 см. Ширина: 43 см. Количество перекладин: 2. Максимальная нагрузка: 15 кг. Вешалка напольная
1217 руб
Раздел: Вешалки напольные
Смываемые фломастеры "Супер чисто", 12 штук.
Дети так любят рисовать! Поэтому набор фломастеров обязательно понравится юным художникам. 12 цветов позволят широко развернуться в
589 руб
Раздел: 7-12 цветов
Кукла Нэни, в вязаном жакете.
Испанская компания Magic Baby представляет серию кукол Нэни (Nany), которые подарят ребенку бесчисленные часы радости и детства! Это
2400 руб
Раздел: Классические куклы
 Большевики и левые эсеры (Октябрь 1917 - июль 1918)

И 4 июля в своем разговоре с "одним членом ЦК" он спросил, не готовил ли, дей ствительно, ЦК ПЛСР "акта партийной оппозиции". Блюмкин показывает: "Вопрос о гарантии ЦК, что в его задачу входит только убийство графа Мирбаха, я задал потому, что вокруг подготовки убийства создалась непроницаемая обстановка, и, кроме того, столкновение на Пятом съезде Советов партии левых с.-р, с правительственной партией сгустило атмосферу политических отношений.. ."66 Блюмкин, конечно же, имел в виду прежде всего агрессивную речь Троцкого, которая посеяла среди левых эсеров панику. Вот что показал по этому поводу Саблин: "...Во время перерыва, после внеочередного заявления Троцкого, Камков мне сообщил о возможности ареста ЦК ПЛСР и даже фракции в связи с возможным обострением отношений с большевиками на этом вечернем заседании.. ."67 Таким образом, уже 5 июля ЦК левых эсеров начал сознавать тот факт, что большевики скорее всего попробуют разделаться с активом их партии. О накале отношений между двумя партиями пишет и Свердлова, утверждая, однако, вопреки показаниям Вацетиса и утверждению Томана, что о предстоящем "восстании" большевики ничего не знали: "Ни Яков Михайлович [Свердлов], конечно, ни кто другой из большевиков не имели достоверных фактов о преступных замыслах левых эсеров, ничего не знали о готовившейся авантюре

скачать реферат Деревья и их свойства (частный вид графов)

Итак, существует взаимно однозначное соответствие между множеством помеченных деревьев с p вершинами и множеством последовательностей вершин s(G). Число таких последовательностей равно, очевидно, pp-2, что и требовалось доказать. Отметим, что среди pp-2 помеченных деревьев с p вершинами могут быть и изоморфные. Определение 3. Подграф G1(X1, E1) неориентированного графа G(X, E) называется каркасом, или остовным деревом графа G, если G1 – дерево и X = X1. Теорема 4. Граф G(X, E) тогда и только тогда обладает каркасом, когда он связен. Доказательство. Необходимость этого очевидна. Докажем достаточность. Пусть G(X, E) – связный граф. Выясним, есть ли в графе G такое ребро, удаление которого не нарушает связности графа G. Если таких ребер нет, то граф есть дерево в соответствии с теоремой 1. Если же такое ребро, например e, существует, то выбросим его и придем к графу G1(X, E {e}). Затем указанную процедуру проделываем с графом G1 и т.д. Через конечное число шагов будет построен, очевидно, каркас графа G. Теорема доказана. Доказательство теоремы дает алгоритм построения некоторого каркаса в связном графе.

 Истинный д'Артаньян

В то же самое время товарищ д'Артаньяна Бемо в свою очередь также не пренебрегал возможностью устроить свои дела. Благодаря отважному поведению в бою он быстро получил повышение: Мазарини назначил его капитаном своей гвардии и помог приобрести большие владения, в частности фьеф Лезер близ Кастра, а также имущество многих дворян, конфискованное по делам о незаконнорожденности или после арестов за участие в дуэли. В сентябре 1653 года Бемо получил от кардинала особо щекотливое дипломатическое поручение. Уже в течение нескольких недель Генрих Лотарингский, граф д'Аркур, по прозвищу «Кадет-Жемчужина» за то, что постоянно носил жемчужную серьгу на манер миньонов Генриха III, присоединился к лагерю Конде и овладел Брейзахом и Филиппсбургом. Задачей Бемо было убедить графа сдать оба города и отказаться от союза с мятежниками. Согласно написанной Мазарини инструкции, его роль состояла в том, чтобы в разговоре с графом д'Аркуром особо подчеркнуть материальные выгоды, которые тот получит, если поведет себя лояльно. Следовало одурманить его красивыми словами

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

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

скачать реферат Принятие управленских решений

Метод “дерева рішень”передбачає, що попередньо зібрана необхідна інформація про очікувані виграші та вірогідності наступу відповідних подій. На практиці цей метод використовується для прийняття рішень у складних ситуаціях, коли результати одного рішення впливають на наступні рішення. Приклад вирішення задачі методом “дерева рішень”. Фірма має кошти для розширення своєї діяльності і повинна вирішити, як ці кошти використовувати найбільш ефективно. Після аналізу ідентифіковано 3 альтернативи: 1) вкласти кошти в придбання нової фірми; 2) вкласти кошти в покращення використання діючих виробничих потужностей; 3) покласти гроші на депозитни рахунок в банк. Для вирішення питання, яка альтернатива найкраща, фірма зібрала необхідну інформацію і побудувала дерево рішень, як опказано на рис. 7. Перша Альтернативи Точка Вірогід- Події Розрахункова величина точка (можливі дії) можли- ність коефіцієнта ROI(%) прийняття востей подій рішення стабільний ріст 15 Покупк а 0,5 нової 0,3 стагнація 9 фірми 0,2 висока інфляція 3 0,5 стабільний ріст 10 Розширення 0,3 стагнація 12 існуючих 0,2 висока інфляція 4 потужностей 0,5 стабільний ріст 6,5 0,3 стагнація 6 Вкладання 0,2 висока інфляція 6 грошей в банк поле дій поле можливих подій поле можливих наслідків Рис.7 Графік "дерева рішення" в задачі інвестування коштів фірми.

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

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

скачать реферат Лекции по ТОЭ

Например, в схеме на рис. 3 ветви 2-6-5; 4-5; 3-6-4; 1 образуют пути между одной и той же парой узлов 1 и 3. Таким образом, путь – это совокупность ветвей, проходимых непрерывно. 2. Контур – замкнутый путь, в котором один из узлов является начальным и конечным узлом пути. Например, для графа по рис. 3 можно определить контуры, образованные ветвями 2-4-6; 3-5-6; 2-3-5-4. Если между любой парой узлов графа существует связь, то граф называют связным. 3. Дерево – это связный подграф, содержащий все узлы графа, но ни одного контура. Примерами деревьев для графа на рис. 3 могут служить фигуры на рис. 4. Рис.4 4. Ветви связи (дополнения дерева) – это ветви графа, дополняющие дерево до исходного графа. Если граф содержит m узлов и ветвей, то число ветвей любого дерева . 5. Сечение графа – множество ветвей, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть отдельным узлом. Сечение можно наглядно изобразить в виде следа некоторой замкнутой поверхности, рассекающей соответствующие ветви. Примерами таких поверхностей являются для нашего графа на рис. 3 S1 иS2 . При этом получаем соответственно сечения, образованные ветвями 6-4-5 и 6-2-1-5.

Стираемая карта "Моя Россия".
Стирамая карта России «Моя Россия» - абсолютная новинка на рынке стираемых карт и наша гордость! Это карта максимально насыщена
921 руб
Раздел: Подарочные наборы
Гель "Meine Liebe" для стирки черных и темных тканей, 800 миллилитров.
Концентрированный гель "Meine Liebe" предназначен для эффективной и бережной стирки черных и темных тканей. Рекомендован для
315 руб
Раздел: Гели, концентраты
Контейнер "Клиер", 15 литров.
Контейнер "Клиер". Материал: пластик. Объем: 15 литров. Длина: 42 см. Ширина: 28 см. Высота: 20 см.
374 руб
Раздел: Штучно
скачать реферат Aлгоритмы на графах

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

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

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе. Замечание. Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1, , vp графа G добавить вершины u1, , up и множество ребер {(vi, ui)} {(ui, vi 1)}. Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v) — по входящим. В отличии от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается P-полной. Большинство известных теорем имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым». Приведем несколько таких теорем. 1.2 Теоремы достаточности гамильтонова графаТеорема (Дирак, 1952) 1. Если в простом графе с e d.

скачать реферат Кодирование информации

При больших значениях и k матрица будет слишком громоздкой, при этом код записывается в сокращенном виде. Матричное представление кодов используется, например, в линейных групповых кодах, кодах Хэмминга и т.д. 3.2 Представление кодов в виде кодовых деревьевКодовое дерево - связной граф, не содержащий циклов. Связной граф - граф, в котором для любой пары вершин существует путь, соединяющий эти вершины. Граф состоит из узлов (вершин) и ребер (ветвей), соединяющих узлы, расположенные на разных уровнях. Для построения дерева равномерного двоичного кода выбирают вершину называемую корнем дерева (истоком) и из нее проводят ребра в следующие две вершины и т.д.Пример кодового дерева для полного кода приведен на рис.1. 1 0 1 0 1 0 1 0 1 0 1 0 1 0 111 110 101 100 011 010 001 000 Рис.1. Дерево для полного двоичного кода при = 3Дерево помехоустойчивого кода строится на основе дерева полного кода путем вычеркивания запрещенных кодовых комбинаций. Для дерева неравномерного кода используется взвешенный граф, при этом на ребрах дерева указываются вероятность переходов. Представление кода в виде кодового дерева используется, например, в кодах Хаффмена. 3.3 Представление кодов в виде многочленовПредставление кодов в виде полиномов основано на подобии (изоморфизме) пространства двоичных - последовательностей и пространства полиномов степени не выше - 1.

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

Содержание Введение Графы, орграфы, деревья Операции над графами Хранение графов в ЭВМ Задача о максимальном потоке Построение максимального потока. Примеры разбираемых задач Литература Введение В коммерческой деятельности большинство возникающих задач удобно представлять для восприятия и анализа в виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как). Коммерческую деятельность можно рассматривать как совокупность задач, предназначенных для передвижения, складирования и распределения товаров, денег, документов, информации о поставках и покупателях воды, нефти, газа, электроэнергии, теле- и радиосистем. Наглядность и логическая обоснованность методов сетевого анализа позволяет выбрать довольно естественный подход к решению задач коммерческой деятельности. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов – области математики, началом развития которой явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 г. Через реку Прегель, на которой стоял город Кенигсберг, построено семь мостов (рис. 1), которые связывали с берегами и друг с другом два острова.

скачать реферат Матрицы графов

Любое подмножество столбцов матрицы B(G) можно рассматривать как матрицу инцидентности Bґ(G) некоторого суграфа Gґ(X, Eґ), содержащего все вершины исходного графа и соответствующее выделенным столбцам подмножество EґCE его ребер. Все столбцы матрицы Bґ(G) линейно независимы тогда и только тогда, когда суграф Gґ(X, Eґ) не содержит циклов. Действительно, если совокупность ребер образует цикл, то каждая вершина инцидента четному числу ребер этого цикла. Следовательно, сумма по модулю 2 соответствующих столбцов дает нулевой столбец, что означает из зависимость. Если же суграф не содержит циклов, то он имеет по меньшей мере две (вообще, четное число) концевых вершин, каждая из которых инцидентна только одному ребру, являющемуся концевым. Поэтому сумма по модулю 2 соответствующих столбцов будет содержать два (или четное число) единичных элемента и, следовательно, совокупность этих столбцов независима. В связном графе с p вершинами всегда можно выделить p-1 ребер так, чтобы они образовали суграф без циклов, представляющий собой дерево графа, являющееся каркасом.

24 восковых мелка для малышей, в бочонке.
Оптимальным выбором карандашей для самых маленьких станет набор из 24 восковых мелков, предназначенных специально для малышей от 1 года.
484 руб
Раздел: Восковые
Фоторамка "Poster blue" (40х60 см).
Рамка настенная может располагаться как вертикально, так и горизонтально. Для фотографий размером: 40х60 см. Материал: пластик.
681 руб
Раздел: Размер 40x60 (А2)
Шарики пластиковые, цветные, 80 штук, диаметр 85 мм.
Пластиковые шарики - веселая игра для малышей, ими можно играть где угодно - дома, на улице, в детском саду, наполнять детский манеж,
529 руб
Раздел: Шары для бассейна
скачать реферат «Биокомпьютеры»

Более глубокое изучение репродуктивной стратегии ресничных инфузорий при сортировке ДНК открывает новые и интересные методы «зацикливания», сворачивания, исключения и инвертирования последовательностей. Напомним, что в 1994 году Леонардом Эдлманом (Leo ard Adlema ) экспериментально было продемонстрировано, как с помощью молекул ДНК в единственной пробирке можно быстро решать классическую комбинаторную «задачу про коммивояжера» (обход вершин графа по кратчайшему маршруту), «неудобную» для компьютеров традиционной архитектуры. Результаты же экспериментов ученых из лейденского центра дают основания надеяться, что в недалеком будущем ресничные инфузории можно будет использовать для реальных ДНК-вычислений. А вот английские исследователи из компании Bri ish elecom пришли к выводу, что изучение поведения колоний бактерий дает ключ к решению сложнейшей задачи упорядочивания коммуникационных сетей. Для описания ближайшего будущего компьютеров сегодня все чаще привлекают популярную концепцию «всепроникающих вычислений» - идею о гигантской совокупности микрокомпьютеров, встроенных во все предметы быта и незаметно взаимодействующих друг с другом.

скачать реферат ТЕОРЕТИЧЕСКИЙ АНАЛИЗ РАСПРЕДЕЛЕНИЯ ФУНКЦИЙ УПРАВЛЕНИЯ В ПОДРАЗДЕЛЕНИЯХ ОМОН И ВНУТРЕННИХ ВОЙСКАХ МВД РОССИИ (низшие структурные подразделения: отделение, взвод)

При решении задачи анализа дерево целей формируется в соответствии с методологией исследования и опытом исследования подобных систем. 2. Декомпозиция задачи производится на подзадачи и далее на более мелкие подзадачи в соответствии с глобальной целью и системой локальных целей. Анализ системы решений подзадач осуществляется с позиции локальных целей и критериев и их соответствия глобальным критериям и целям. В данном случае цели выступают как ограничения. В результате этого этапа осуществляется постановка решения задачи как анализа, так и синтеза. Например, синтез силовой системы для выполнения наступательной или оборонительной операций или анализ разведывательных данных с целью исследования обороны противника (бандитских формирований). 3. Математическое моделирование и разработка программного обеспечения выполняются для решения локальных задач синтеза или анализа. Этот этап чисто технический, но в связи с тем, что не всегда существуют типовые математические модели и необходимое программное обеспечение, для решения рассматриваемых задач допускается применение итерационных процедур разработки и уточнения операции каждого этапа.

скачать реферат Цели в системе управления

Исключение хотя бы одной подцели лишает полноты или меняет само понятие исходной цели. Представление главной цели в виде дерева целей может оказаться неполным, так как могут быть потеряны присущие её свойства. Проблема полноты в этом случае решается за счет квалификации эксперта, формирующего полное описание, и использования более сложных структур, например, путем превращения дерева целей в граф более общего вида. Оценка важности целей может быть выражена в их ранжировании. В этом случае каждой цели приписывается порядковый номер, показывающий её относительную важность для достижения соответствующей цели более высокого уровня. Другим способом является нормирование по значимости. Многие цели по своей природе не поддаются формализации, и, следовательно, их не удается точно измерить. Другие же цели измеримы, но их величины несопоставимы одна с другой. Поэтому, чтобы осуществить общее ранжирование всего дерева целей, используются условные показатели и оценки. Ранжирование и нормирование целей часто осуществляется на основе метода экспертных оценок. При этом на основе индивидуальных оценок выводят общую усредненную оценку.

скачать реферат Формирование у учеников ответственного отношения к учебе во время самостоятельной работы

За навчальними цілями і змістом задачі природничо-наукового характеру не однорідні. Одні стимулюють більш глибоке засвоєння теоретичних питань, зокрема законів, тому їх слід віднести до групи теоретичних задач; другі допомагають школярам глибше осмислити практичні питання і отже можуть бути віднесені до групи практичних задач; треті об’єднують в собі і теоретичні і практичні запитання і забезпечують одночасне вдосконалення і теоретичних і практичних знань учнів . Спільною ознакою всіх трьох навчальних задач є те, що кожна з них може мати кількісний або якісний характер, в залежності від тих питань, які обов’язково входять в зміст любої задачі і які повинні бути обчислені. Нерідко ці ознаки об’єднуються. Зміст і навчальні цілі обумовлюють також різноманітність прийомів розв’язування задач. Вчителі широко використовують письмові, графічні та інші прийоми, причому число їх поєднується. Є також і усний прийом, але задачі такого роду мають переважно тренувальний характер і стимулюють в основному процесі пам’яті. Приведене угрупування відображає лише зовнішні відмінності задач, внутрішня ж сторона процесу вирішення задач як методу самостійної роботи єдина.

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

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