WinNavigator

Frigate

Norton Commander

WinNC

Dos Navigator

Servant Salamander

Turbo Browser

Winamp, Skins, Plugins

Необходимые Утилиты

Текстовые редакторы

Юмор

File managers and best utilites

Курсовая работа: Графы. Реферат графы в математике

Реферат Граф (математика)

скачать

Реферат на тему:

План:

1 Определения
- 1.1 Граф
- 1.2 Ориентированный граф
- 1.3 Смешанный граф
- 1.4 Изоморфные графы
- 1.5 Прочие связанные определения
- 1.6 Дополнительные характеристики графов
- 1.7 Список рёбер
2 Обобщение понятия графа

Введение

Неориентированный граф с шестью вершинами и семью рёбрами

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин.

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — гиперссылки (см. Тематическая карта).

1. Определения

Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения — наиболее часто встречаемые.

1.1. Граф

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

V это непустое множество вершин или узлов,
E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

V (а значит и E, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

1.2. Ориентированный граф

Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:

V это непустое множество вершин или узлов,
A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга $v \to w$ ведёт от вершины v к вершине w.

1.3. Смешанный граф

Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

1.4. Изоморфные графы

Граф G называется изоморфным графу H, если существует биекция f из множества вершин графа G в множество вершин графа H, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и наоборот — если в графе H есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины f − 1(A) в вершину f − 1(B). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

1.5. Прочие связанные определения

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

Ориентированным путём в орграфе называют конечную последовательность вершин vi $(i=1,\ldots,k)$ , для которой все пары (vi,vi + 1) $(i=1,\ldots k-1)$ являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
Всякий простой неэлементарный путь содержит элементарный цикл.
Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
Петля — элементарный цикл.

Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v», является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов

Ребро графа называется мостом, если его удаление увеличивает число компонент.

1.6. Дополнительные характеристики графов

Граф называется:

связным, если для любых вершин u,v есть путь из u в v.
сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
деревом, если он связный и не содержит простых циклов.
полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
двудольным, если его вершины можно разбить на два не пересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2.
k-дольным, если его вершины можно разбить на k не пересекающихся подмножества V1, V2, …, Vk так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.

Также бывает:

k-раскрашиваемым
k-хроматическим

1.7. Список рёбер

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

2. Обобщение понятия графа

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

Более абстрактно, граф можно задать как тройку $(V, E, \varphi)$ , где V и E — некоторые множества (вершин и рёбер, соотв.), а $\varphi$ — функция инцидентности (или инцидентор), сопоставляющая каждому ребру $e\in E$ (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:

ориентированные графы (орграфы) — когда $\varphi(e)$ всегда является упорядоченной парой вершин;
неориентированные графы — когда $\varphi(e)$ всегда является неупорядоченной парой вершин;
смешанные графы — в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
Эйлеровы графы — граф в котором существует циклический эйлеров путь (Эйлеров цикл).
мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
псевдографы — это мультиграфы, допускающие наличие петель;
простые графы — не имеющие петель и кратных рёбер.

Под данное выше определение не подходят некоторые другие обобщения:

гиперграф — если ребро может соединять более двух вершин.
ультраграф — если между элементами xi и uj существуют бинарные отношения инцидентности.

Литература

Оре О. Теория графов. М.: Наука, 1968. 336с. http://eqworld.ipmnet.ru/ru/library/books/Ore1965ru.djvu
Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с. http://eqworld.ipmnet.ru/ru/library/books/Uilson1977ru.djvu
Харари Ф. Теория графов. М.: Мир, 1973. http://eqworld.ipmnet.ru/ru/library/books/Harari1973ru.djvu
Кормен Т. М.и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. — 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf

wreferat.baza-referat.ru

Курсовая работа - Графы - Математика

Реферат по математике ученика 8 г класса Коротаева Дмитрия

Муниципальное образовательной учреждение – МОУ Гимназия №47

Екатеринбург, 2000

Введение

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, — работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

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

Понятие о графах

Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» — пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог (рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами.

Использует графы и дворянство. На рисунке 2 приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками.

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

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

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

Графы, изображенные на рисунках 4 и 5, как оказалось, играют решающую роль при определение для каждого графа – является ли он плоским, то есть может ли он быть изображен на плоскости без пересечения его ребер. Польский математик Г. Куратовский и академик Л. С. Понтрягин независимо доказали, что если граф не является плоским, то в нем «сидит» хотя бы один из графов, изображенных на рисунках 4 и 5, то есть «полный пятивершинник» или граф «домики – колодцы».

Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, — работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.

Стрелка от одой работы к другой на графе, изображенном на рис. 7, означает последовательность выполнения работ. Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду и т. д.

Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.

На рис.8 изображена схема дорог между селами М, А, Б, В, Г.

Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развезти письма по остальным четырем селам. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф(внизу), на котором легко увидеть возможные маршруты. Вершина М вверху – начало маршрутов. Из нее можно начать движение четырьмя различными способами: вА, в Б, в В, в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4 3 2 1 = 24 способа.

Расставим вдоль ребер графа цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28км, соответствующие маршрутам М-В-Б-А-Г-М и М-Г-А-Б-В-М. Это один и тот же путь, но пройденный в разных направлениях Заметим, что граф на рис. 8 тоже можно сделать направленным, указав направление сверху вниз на каждом из ребер, что соответствовало бы направлению движения почтальона. Подобные задачи часто возникают при нахождении лучших вариантов развозки товаров по магазинам, стройматериалов по стройкам.

Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В — в меньшей. В начальный момент ситуация описывалась тройкой чисел ( 8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: ( 3, 5, 0), если наполним водой большую кастрюлю, или ( 5, 0, 3), если наполним меньшую кастрюлю.

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Подобным образом можно ставить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов», где позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки.

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

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

Впервые основы теории графов появились в работе Л. Эйлера, где он описывал решение головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х гг. 20 в. в связи со становлением кибернетики и развитием вычислительной техники.

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

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

Вот несколько задач теории графов. Задача об эйлеровом пути: найти путь по ребрам графа, проходящий по каждому ребру ровно один раз. Такой путь существует лишь в том случае, если граф – связный, т. е. от каждой его вершины к каждой другой можно пройти по ребрам графа, и из каждой вершины, кроме, может быть, двух, выходит четное число ребер. На графе, изображенном на рис. 3, а, он есть, а на рис. 3, б его нет.

Хроматическим числом графа называется наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединенные ребром, окрашиваются при этом в разные цвета. Долгое время математики не могли решить эту проблему: достаточно ли четырех красок, для того чтобы раскрасить произвольную графическую карту так, чтобы любые две стороны, имеющие общую границу, были окрашены разными красками? Если изобразить страны точками – вершинами графа, соединив ребрами те вершины, для которых соответствующие им страны граничат, то задача сведется к следующей: верно ли, что хроматическое число любого графа, расположенного на плоскости, не больше четырех? Положительный ответ на этот вопрос был лишь недавно получен с помощью ЭВМ.

Используя графы можно решать задачи. Вот, например, как выглядит последняя американская версия известной задачи Дьюдени:

1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями. В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р)

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир – однофамилец кондуктора живет в Чикаго.

6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь.

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста?

Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы).

Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.

Заключение

В настоящем реферате рассмотрены математические графы, области их применения, решено несколько задач с помощью графов. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты). Кроме того, работая над рефератом, я освоил работу на компьютере в текстовом редакторе WORD. Таким образом, задачи реферата выполнены.

Список литературы

1. Энциклопедический словарь юного математика\Сост.А.П.Савин.- М.: Педагогика, 1989

2. Квант №6 1994г.

3. М.Гарднер «Математические досуги»М.: Мир, 1972

www.ronl.ru

Реферат: Графы

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

Понятие о графах

Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог (рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами.

Возможно вы искали - Реферат: Алгебра матриц

Похожий материал - Доклад: О гравитации и необнаруживаемой гравитационной волне

Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.

Очень интересно - Реферат: Опыты Саньяка, Майкельсона – Гаэля, Миллера

Около вершин графа указаны числа – продолжительность в днях соответствующей работы . Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.

На рис.8 изображена схема дорог между селами М, А, Б, В, Г.

Вам будет интересно - Реферат: Отклонение лучей света в космосе

Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел ( 8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: ( 3, 5, 0),если наполним водой большую кастрюлю, или ( 5, 0, 3), если наполним меньшую кастрюлю.

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Похожий материал - Реферат: Опыты Араго и теория Френеля

Вот несколько задач теории графов. Задача об эйлеровом пути: найти путь по ребрам графа, проходящий по каждому ребру ровно один раз. Такой путь существует лишь в том случае, если граф – связный, т. е. от каждой его вершины к каждой другой можно пройти по ребрам графа, и из каждой вершины, кроме, может быть, двух, выходит четное число ребер. На графе, изображенном на рис. 3,а, он есть, а на рис. 3,б его нет.

cwetochki.ru

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

Графы

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

Понятие о графах

$C:\Users\Дима\Desktop\41209\41209~001.gif$

$C:\Users\Дима\Desktop\41209\41209~002.gif$

$C:\Users\Дима\Desktop\41209\41209~003.gif$ $C:\Users\Дима\Desktop\41209\41209~004.gif$

Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.

Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.

Около вершин графа указаны числа – продолжительность в днях соответствующей работы . Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.

На рис.8 изображена схема дорог между селами М, А, Б, В, Г.

В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.

Вот несколько задач теории графов. Задача об эйлеровом пути: найти путь по ребрам графа, проходящий по каждому ребру ровно один раз. Такой путь существует лишь в том случае, если граф – связный, т. е. от каждой его вершины к каждой другой можно пройти по ребрам графа, и из каждой вершины, кроме, может быть, двух, выходит четное число ребер. На графе, изображенном на рис. 3,а, он есть, а на рис. 3,б его нет.

Хроматическим числом графа называется наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединенные ребром, окрашиваются при этом в разные цвета. Долгое время математики не могли решить эту проблему: достаточно ли четырех красок, для того чтобы раскрасить произвольную графическую карту так, чтобы любые две стороны, имеющие общую границу, были окрашены разными красками? Если изобразить страны точками – вершинами графа, соединив ребрами те вершины, для которых соответствующие им страны граничат , то задача сведется к следующей: верно ли, что хроматическое число любого графа, расположенного на плоскости, не больше четырех? Положительный ответ на этот вопрос был лишь недавно получен с помощью ЭВМ.

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир – однофамилец кондуктора живет в Чикаго.

6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь.

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста?

$C:\Users\Дима\Desktop\41209\41209~005.gif$

Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы).

Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.

www.coolreferat.com

Смотрите также

..:::Новинки:::..

Windows Commander 5.11 Свежая версия.

Новая версия
IrfanView 3.75 (рус)

Обновление текстового редактора TextEd, уже 1.75a

System mechanic 3.7f
Новая версия

Обновление плагинов для WC, смотрим :-)

Весь Winamp
Посетите новый сайт.

WinRaR 3.00
Релиз уже здесь

PowerDesk 4.0 free
Просто - напросто сильный upgrade проводника.

..:::Счетчики:::..