Реферат на тему графы дискретная математика

Варфоломей

Опубликовано Полева Ирина Александровна вкл Красные желтые вершины графа G , на каждом шаге алгоритма, образуют красный желтый если это не возврат для распознания перешейков — укорачивается, при распознавании обратного ребра и перешейков — не изменяется. Проверьте почту. Основные теоремы теории графов………………………………………6 5. Многие известные головоломки могут быть изложены на языке теории графов. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины.

Понятие "жадный алгоритм", его свойства. Применение формул метода Дейкстры для решения экономических задач. Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.

Рекомендуем скачать работу и оценить ее, кликнув по соответствующей звездочке. Главная База знаний "Allbest" Математика Основные понятия теории графов - подобные работы. Основные понятия теории графов Теория графов как область дискретной математики с геометрическим подходом к изучению объектов. Решение математических развлекательных задач и головоломок.

Эйлеров путь графа. Краткие пути решения. Задача коммивояжера - одна из задач теории комбинаторики. Мы будем рассматривать графы, у которых число вершин и число рёбер. Задача 1. Между девятью планетами солнечной системы установлено реферат на тему графы дискретная математика сообщение.

2398748

Можно ли долететь на рейсовых ракетах с Земли до Марса? Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу? А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:. Задача 3.

Реферат на тему графы дискретная математика 1893556

Докажите, что из столицы можно долететь в город Дальний. Рассмотрим компоненту связности, которая включает в себя столицу Царства.

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

Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний — по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности — связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Предложение 1. Следствие 1. В частности, если k — нечётное число, то число вершин является чётным. Следствие 2. Упражнение 1. Упражнение 2.

Реферат на тему графы дискретная математика 7027

Можно ли соединить между собой проводами 7 телефонов так, чтобы каждый был соединен ровно с тремя другими? Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины.

Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.

Понятия смежности и инцидентности. Основные задачи исследования: 1. Структуры данных Постановка задачи. Введение в дискретную математику: элементы комбинаторики, теории графов и теории кодирования. Графы, в которых построены все возможные ребра, называется полным.

Эта закономерность справедлива для любого графа. Такой граф называется уникурсальным.

Графы

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

Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш? Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, пунктирная — не лежит рис 4.

Затем достраиваем граф по следующему правилу: так как в коробке лежит только один карандаш, то из каждой точки должны выходить одна сплошная и три пунктирные линии. Рис 8. Первенство проводилось по круговой схеме: каждый из участников играет реферат на тему графы дискретная математика каждым из остальных один. Сколько пар проведено и сколько еще осталось?

Изобразим данные задачи в виде схемы. Участники — это точки, сплошные линии — это сыгранные партии, пунктирные линии — это несыгранные партии. Следовательно, проведено 7 игр, осталось провести — 8 игр.

Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три. Сколько лет Лене? Ответ: Юре — 8 лет, Тане — 13 лет, Свете -5 лет, Лене — 15 лет. Он применил ее для решения систем линейных уравнений, описывающих работу электрических цепей. Развитие теории графов деревьев связано с именем немецкого химика Кели, который успешно применил ее для решения задач органической реферат на тему графы дискретная математика для изучения изомеров углеводородов с заданным числом атомов.

Реферат на тему графы дискретная математика 9102

Если все вершины графа принадлежат дереву, то он называется покрывающим. Пусть дано множество вершин графа. Одну из вершин, например х 1примем за начальную, которую назовем корнем дерева. Из этой вершины проводим ребра к остальным вершинам х 2х 3 и т. Если добавить ребро, то добавляется и вершина. Таким образом, дерево с п вершинами имеет n-1 ребро. Дерево имеет корень в вершине В р если существует путь от х 1к каждой из вершин.

Исследование среды — это своего рода дискретная система, представленная как модель взаимодействия управляющей и управляемой систем, взаимодействие которых зачастую представляется как процесс перемещения управляющего автомата по графу управляемой системы. Запишем матрицу смежности 5, для ориентированного графа, изображенного на рисунке 7: Матрицей инциденции Т размера m x n называется матрица, состоящая из чисел: Запишем матрицу инциденции для графа, изображенного на рисунке 7: Операции над графами Объединением двух, или более графов G 1 , U G 2 U … U G n называется граф, у которого множество вершин и множество дуг объединены рис.

Ребра графа, принадлежащие дереву, называют ветвями, остальные ребра называют хордами. Граф называется планарным, если он может быть изображен на плоскости таким образом, что его ребра будут пересекаться только в планарных вершинах рис. Дерево, являющееся подграфом графа Gназывается покрывающим граф Gесли оно содержит все его вершины. Пусть имеется х 1х 2 ,…, х n вершин и u 1u 2 …, u m дуг, их содержащих. Матрицей смежности S порядка п называется матрица, состоящая из чисел S.

Матрица смежности для ориентированного и неориентированного графа, вообще говоря, имеет разный вид.

Реферат по информатике информация и человекОсновные блоки пк и их назначение реферат
Отчет о производственной практике логиста на предприятииРецензия на басню квартет

Запишем матрицу смежности 5, для ориентированного графа, изображенного на рисунке Матрицей инциденции Т размера m x n называется матрица, состоящая из чисел:. Объединением двух, или более графов G 1U G 2 U … U G n называется граф, у которого множество вершин и множество дуг объединены рис. Суммой графов G 1 и G 2 называется граф, определяемый как объединение графов, причем каждая вершина, не вошедшая в объединение, соединяется с другими вершинами рис.

Будем говорить, что вершина и j конусирует граф Gесли она смежная со всеми вершинами графа.

Доклад на тему "Графы и их применение при решении задач"

Рассмотрим подробно решение задачи о Кенигсбергских мостах. В городе Кенигсберге имеется остров Кнайпхоф, который охвачен двумя рукавами реки Пречель. Можно ли спланировать прогулку таким образом, чтобы по каждому мосту пройти только один раз и вернуться в начальное положение? Поставим в соответствие каждому мосту ребро графа, а суше вершину рис. Эйлеровым путем в графе G называется такой путь в котором каждое ребро встречается один.

Эйлер доказал, что такой путь существует тогда и только тогда, когда граф G содержит не более двух вершин нечетной степени и являются связными. В данной задаче существует четыре вершины нечетной степени 5, 3, 3, 3. Таким образом, задача о Кенигсбергских мостах не содержит Эйлеров путь и не имеет решения. Если граф содержит точно реферат на тему графы дискретная математика вершины нечетной степени, то в эйлеровом пути эти вершины должны быть конечными. На рисунке 12, а нет замкнутого эйлерова пути; на рисунке 12, б эйлеров путь замкнут.

Теорема 4. В любом конечном графе сумма степеней вершин равна удвоенному числу его ребер. Гамильтон придумал игру, состоящую в том, что на доске располагались города в виде додекаэдра рис. Играющий игрок должен обозначить шнуром замкнутый круг, соединяющий последовательно одну вершину с другой, посетив при этом все города, зайдя в каждый только один. Граф G называют Гамильтоновым, если он содержит простейший путь, проходящий через его вершину.

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

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

Математически эта задача решения не имеет. Дерево игры — это способ описания игры, в которой последовательно, по ходам, фиксируется, какой информацией должны располагать игроки, какие варианты они могут выбрать, а также средний размер платежей в конце игры.

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

Узлы выбора различны. Дерево решений применяется тогда, когда количество альтернатив и принятых решений. Построение деревьев решений используют при решении задач динамического распределения памяти ЭВМ. В динамическом программировании решение задачи планирования работ называют проектом.

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

Существуют два способа математического решения этой задачи. Деппа описывающих обход шахматных лабиринтов конечными реферат на тему графы дискретная математика. В дальнейшем Г. Дудеком проводились исследования в области анализа свойств неизвестной среды при различных способах взаимодействия автомата с операционной средой, а также при различной априорной информации о. Анализ графа включает в себя ряд частных задач, основными из которых есть: проблема самолокализации определения вершины графа, в которой первоначально находиться автоматпроблема контроля карты проверки изоморфизма исследуемого графа и графа-эталона карты и проблема полного распознавания графа.

В работе И. Грунского и Е. Татаринова предложен метод распознавания графа одним агентом, базирующийся на стратегии поиска в глубину. Начиная с года Г. Дудек публикует работы по исследованию графов роем агентов. Алгоритм работы роя заключается в следующем: все агенты память агента должна быть такой, чтобы могла вместить карту всего графа начинают работу с одной вершины; договорившись заранее о времени следующей встречи, они делят доступные ребра между собой и расходятся по ним; обходят о пределенную часть графа и возвращаются в исходную вершину для объединения полученных карт; договариваются о следующей встрече и снова расходятся и так продолжается до полного распознавания.

Исследованию графа при помощи одного агента посвящено много работ, получено множество результатов реферат на тему графы дискретная математика возможности и сложности такого распознавания. При этом остается малоисследованно распознавание графа коллективом блуждающих по нему агентов. Это делает актуальной задачу проведения систематического исследования экспериментов по распознаванию графа несколькими блуждающими по нему агентами, то есть создания маршрутов движения агентов по неизвестному графу, разметки его элементов, сбора и обработки локальной информации о графе и способов построения графа по этой информации, с точностью до отметок на элементах графа [ 7 ].

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

Белоусова Татьяна Владимировна

При обходе агентами графа в глубину, реферат на тему графы дискретная математика вершине ставится в соответствие номер по порядку неявно. В процессе обхода посещенные вершины, у которых восстановлены не все инцидентные им ребра образуют простые, непересекающиеся пути.

Каждый из этих путей может быть однозначно пройден агентом, построившим этот путь, в прямом и обратном направлении. Рассмотрим базовый алгоритм распознавания графов коллективом агентов с использованием неявной прямой нумерации вершин. Вход: граф G неизвестный агентам-исследователям и агенту-экспериментатору, все элементы графа G окрашены краской w, агент A помещен в произвольную вершину v.

В случае обнаружения смежной вершины, окрашенной в чужой цвет, агент метит все перешейки из текущей вершины в чужую область и сообщает второму АИ, через агента-экспериментатора, о необходимости распознавания помеченных перешейков. Пока второй АИ распознает перешейки, первый АИ не может метить новые перешейки. В случае отсутствия других возможных вариантов перемещения, кроме как пометить новый перешеек, первый АИ останавливается до того момента, пока второй АИ не распознает все помеченные перешейки [ 1 ].

Рисунок 2 — Работа агентов исследователей анимация: объем — КБайт, количество кадров — 11, размер — х На основе этой нумерации и происходит восстановление графа G, путем построения изоморфного ему графа H.