Графы, деревья — в помощь студенту

Графы, деревья - в помощь студенту

С.Н. Андреянова

alt

Узнай стоимость своей работы

Бесплатная оценка заказа!

Оценим за полчаса!
  • ТЕОРИЯ ГРАФОВ
  • Краткое учебное пособие по теории графов:
  • Основные идеи, темы,
  • типы задач
  • СОДЕРЖАНИЕ

Введение…….………………………………………………………………………………………..5

Раздел 1.Теория графов как раздел прикладной математики…………………………………….6

§1. Сведения из истории графов…………………………………………………………………….6

§2. Понятие, элементы, виды и способы задания графов……………………………………..…..7

§3. Эйлеров и гамильтонов циклы. Рисование фигур единым росчерком……………………..16

alt

Узнай стоимость своей работы

Бесплатная оценка заказа!
Читайте также:  Защита от несанкционированного доступа к информации - в помощь студенту

Оценим за полчаса!

Раздел 2. Графы и правильная раскраска карты…………………………………………………..19

§1. «Задача четырех красок». Графы и правильная раскраска карты……………………….….19

Раздел 3. Графы с цветными ребрами…………………………………………………….…….…21

§1.Графы с цветными ребрами……………………..……………………………………..….……21

§2. Свойства графов с цветными ребрами………………………………………………….….…22

Раздел 4. Графы и лабиринты. …………………………………………………………….………28

§1.Графы и лабиринты……………………………………………………………………………….……..….28

§2.Способы прохождения лабиринта…………………………………………………….………..31

Раздел 5. Применение теории графов………….………………………………………………….33

§1. Применение графов в различных сферах научной деятельности…..……………………….33

§2. Решение задач на применение графов в различных областях жизни………………………36

§3. Разработка генеалогического древа с помощью графа………………………………………39

Раздел 6. Теория графов в решении задач…………..………………………………………..…..40

§1.Теория графов при решении олимпиадных задач…………………………………………….40

§2.Теория графов при решении задач ЕГЭ………………………………………………..………41

Приложение. Задания для индивидуальной работы………………………………………..…….47

Словарь терминов…………………………………………………………………………….……56

Заключение………………………………………………………………………………………….58

Библиография………………………………………………………………………………..……..59

Предисловие

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

В книге вы сможете познакомиться с основами теории графов, которые помогут вам в решении самых разнообразных задач.

Введение

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

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

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

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

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

Раздел 1.Теория графов как раздел прикладной математики.

§1. Сведения из истории графов.Графы, деревья - в помощь студенту

Родоначальником теории графов является математик Леонард Эйлер, решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кенигсбергских мостов. В городе Кенигсберге (ныне Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рис. 1.1.1.

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

Исключительный вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.

Графы, деревья - в помощь студенту

Рис. 1.1.1 Рис. 1.1.2

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост — линией (ребром), соединяющий соответствующие точки. Получился «граф». Он показан на рис. 1.1.2, где точки отмечены теми же буквами, что и четыре части суши на рис. 1.1.1.

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

Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и нашел критерий существования обхода у данного графа, а именно граф должен быть связным, и каждая его вершина должна быть инцидента четному числу ребер. Граф, показанный на рис. 1.1.2, связный, но не каждая его вершина инцидентна четному числу ребер.[15, с. 13-15].

§2. Понятие, элементы, виды и способы задания графов.

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

Задача 1.В государстве Морляндия находятся 8 крупных островов, некоторые из которых соединены радиосвязью. Связь есть между следующими островами:

  1. Банановый – Кокосовый;
  2. Кукуру – Рыбный;
  3. Столичный – Акулий;
  4. Птичий – Кукуру;
  5. Одинокий – Столичный;
  6. Акулий – Одинокий;
  7. Столичный – Кокосовый;
  8. Птичий – Рыбий.

Можно ли послать сообщение с острова Банановый на остров Акулий? А с острова Акулий на Рыбный?

Графы, деревья - в помощь студенту

Рис.1.2.1.

Решение. Нарисуем схему радиосвязи. Острова обозначим точками (вершинами), радиосвязь линиями (ребрами). Из схемы видно, что с острова Банановый на остров Акулий послать сообщение, а с острова Акулий на Рыбный – нет. Отсюда делаем вывод:

Граф – это фигура, состоящая из точек (вершин) и отрезков (ребра), соединяющих эти точки.

Графы, деревья - в помощь студенту

Рис. 1.2.2. Граф

Если две вершины графа соединены более чем одним ребром, то каждое такое ребро называется кратным. Вершины и рёбра графа называются также элементамиграфа, число вершин в графе — порядком, число рёбер — размером графа. Ребро называется петлёй, если его концы совпадают. Вершина называется изолированной, если она не является концом ни для одного ребра. Ребро называется инцидентным вершине, если она является одним из его концов. [10, с. 184-188].

Задача 2. В 10-значном числе каждые две подряд идущие цифры образуют двузначное число, которое делится на 13. Докажите, что среди этих цифр нет цифры 8.

Решение. Существует 7 двузначных чисел, которые делятся на 13. Обозначим эти числа точками, и, если вторая цифра одного числа совпадает с первой цифрой другого числа, соединим их линией. Видим, что если 10-значное число обладает заданным свойством, то оно состоит из периодически повторяющихся цифр…1391 или …6526… Цифры 8 быть не может.

Графы, деревья - в помощь студенту

Рис.1.2.3.

Лемма 1.Число ребер в графе ровно в два раза меньше, чем сумма степеней вершин.

Графы, деревья - в помощь студенту

Рис.1.2.4.

Число ребер, сходящихся в вершине, называют степенью вершины.

Задача 3. В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок проходит между домами?

Решение. Пусть дома – вершины графа, тропинки – ребра. Тогда степень каждой вершины равна 7, всего сумма степеней вершин 7*10=70, тогда число ребер (тропинок) 70:2=35

Лемма 2.Число нечетных вершин графа четно.

Графы, деревья - в помощь студенту

Рис.1.2.5.

Задача 4.Маша сказала своей подружке Лене: «У нас в классе двадцать пять человек. И представь, каждый из них дружит ровно с семью одноклассниками». «Не может этого быть», — ответила Лена. Почему она так решила?

Решение. Представим себе, что между каждыми двумя друзьями протянута веревочка. Тогда каждый из 25 учеников будет привязан к 11 концам веревочек, и значит, всего у протянутых веревочек будет 25*7 = 175 концов. Но их общее число не может быть нечетным, так как у каждой веревочки 2 конца.

Лемма 3. В полном графе с n вершинами число ребер равно

Задача 5.Сколько диагоналей в 17-угольнике?

Решение. Вершины 17-угольника – вершины графа, диагонали и стороны – ребра графа. Всего

17*(17-1):2=136 ребер. Из них 17 сторон, остальные – диагонали. Значит диагоналей

136-17=119.

Задача 6. Ваня и Миша играют в такую игру. Они по очереди связывают 5 столбиков ленточками попарно. Кто свяжет последнюю пару столбиков, тот выиграл. Кто победит – тот, кто завяжет первую ленточку, или его соперник?

Решение. После того, как все ленты будут завязаны, получится полный граф с 5 вершинами-столбиками и ребрами-ленточками. В этом графе 5*(5-1):2=10 ребер. Значит, выиграет тот, кто завязывал ленту вторым, потому что второй завязывает четные ленточки, а первый – нечетные.

Задача 7. Написано 2009-значное число. Каждое двузначное число, образованное соседними цифрами этого числа, идущими в той же последовательности, делится на 23 или на 17. Последняя цифра 7. Какая цифра первая?

Решение.Двузначные числа, которые делятся на 23- 23, 46, 69, 92. Двузначные числа, которые делятся на 17-17, 34, 51, 68, 85. Нарисуем граф, в котором вершинами будут цифры. Соединим их дугами, если они составляют число, которое делится на 23 или на 17.

Так как в числе 2009 цифр и последняя 7, то до этого обязательно стояли цифры 1, 5, 8, 6, а потом цифры в обратном порядке повторялись: 6-4-3-2-9-6-4-…, при этом в цикле 5 цифр. На них остается 2009-4=2005 цифр, то есть целое число циклов. Цикл начался с 6, значит, последняя цифра цикла 9.

Так как мы двигались от последней цифры к первой, то 9 – это и есть первая цифра 2009-значного числа.

Графы, деревья - в помощь студенту

Рис.1.2.6.

Граф называется связным, если все его вершины связаны. Графы, деревья - в помощь студенту

Рис. 1.2. 7. Связный граф Рис. 1.2.8. Несвязный граф

Задача 8. В кабинете стоит несколько приборов и одна розетка, при этом некоторые из них соединены проводами. Все концы проводов подключены к приборам, и один конец подключен к розетке. От компьютера отходят 7 проводов, а от всех остальных приборов по 4. Докажите, что компьютер соединен с розеткой (может быть, через другие приборы).

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

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

В дереве с n вершинами n-1 ребер.

Задача 9. В государстве Морляндия 17 островов, между ними проложены маршруты так, что с каждого острова выходит ровно четыре маршрута. Докажите, что в Морляндии есть такие два острова, что с одного до другого можно добраться двумя разными путями (но может быть, с пересадками на других островах).

Решение. Представим себе острова вершинами графа, а маршруты – ребрами этого графа. В таком графе сумма степеней вершин равна 17*4, и значит, в нем 17*4:2=34 ребра.

Если в этом графе есть цикл, то между любыми вершинами цикла есть два пути – с противоположным направлением обхода.

Если же циклов в этом графе нет, то граф является деревом или состоит из нескольких деревьев, а в любом дереве число ребер на 1 меньше числа вершин. Но у нас в графе ребер больше, чем вершин, значит, в графе есть цикл.

Задача 10. Маша и Саша любят играть в такую игру: в рыболовной прямоугольной сетке размером 4х5 ячеек по очереди перерезают по одной веревочке так, чтобы сетка не распалась на куски. Победителем станет тот, кто разрежет последнюю веревочку. Кто выиграет при правильной игре?

Читайте также:  Социально-экономические отношения критского государства - в помощь студенту

Решение. Представим узлы сетки вершинами, а веревочки – ребрами графа. В начале игры было 5*6 = 30 вершин и 5*5+4*6=49 ребер.

Рис.1.2.9.

Можно удалять ребра до тех пор, пока в графе остались циклы. Как только граф станет деревом, при удалении любого ребра он перестанет быть связным, и игрок не сможет сделать ход. Вершин при этом осталось 30, и ребер стало 30-1=29. За игру будет удалено 49-29=20 ребер, последний ход сделает второй игрок и выиграет.

Виды графов.

Рис. 1.2.10. Ориентированный граф.

Источник: https://infourok.ru/posobie-po-teorii-grafov-3550951.html

Применение графов в различных областях жизни людей | Обучонок

Исследовательская работа: 

Исследовательская работа «В мире графов»

Глава 2. Возможности применения теории графов в различных областях повседневной жизни

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

1.

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

2. Лабиринт.

Графы, деревья - в помощь студенту
Исследовать лабиринт — это найти путь в этом графе.

Вершинами здесь обозначены тупики, а отрезками – проходы лабиринта. (приложение 1, рис. 2)

3. Генеалогическое древо.

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

Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка – обозначенный ею объект входит в один класс верхнего уровня.

Любая вершина дерева может порождать несколько потомков – вершин, соответствующих классам нижнего уровня.

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

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

(приложение 1 рис.4).

5. Схема цепей дежурного освещения

Графы, деревья - в помощь студенту
Схема цепей дежурного освещения тепловоза ТЭМ2 тоже представлена в виде графа.

(приложение 1 рис.5).

6. Схемы авиалиний

Графы, деревья - в помощь студенту
Схемы авиалиний представлены в виде графов.

(приложение 1 рис.6).
7. Участок московского Метрополитена.
Графы, деревья - в помощь студенту
Один из участков московского Метрополитена.

Он нарисован тоже в виде графа.

(приложение 1 рис.7).

8. Социограммы

Графы, деревья - в помощь студенту
Социограммы (в психологии при исследовании межличностных отношений в группах).

Она тоже представлена с помощью графа.

(приложение 1 рис.8).

9. Схема железных дорог

Графы, деревья - в помощь студенту
Схема железных дорог.

Вершины – железнодорожные станции, а рёбра – железнодорожные пути.

(приложение 1 рис.9).

10. Созвездия
Графы, деревья - в помощь студенту
Графы есть и на картах звездного неба.

Это созвездия.

(приложение 1 рис.10).

11. Химия.

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

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

12. Математика. Немало поводов для появления графов и в математике. Наиболее очевидный пример – любой многогранник в трёхмерном пространстве.

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

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

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

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

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

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

Источник: https://obuchonok.ru/node/1321

2.5. Минимальное остовное дерево

Найти минимальное остовное дерево в неориентированном нагруженном графе.

Алгоритм выделения минимального остовного дерева в неориентированном нагруженном графе G

1) Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G2 графа G. Положим I:=2.

2) Если I=N(G), то задача решена и Gi – искомое минимальное остовное дерево графа G. Иначе переходим к шагу 3).

3) Строим граф Gi+1. Для этого добавим к графу Gi новое ребро минимальной длины из оставшихся, которое инцидентно какой-либо вершине графа Gi и одновременно вершине, не содержащейся в Gi. Вместе с этим ребром включаем в Gi+1 и эту инцидентную ему вершину. Присваиваем I:=I+1 и переходим к шагу 2).

Пример.

Найдем минимальное остовное дерево в неориентированном нагруженном графе, изображенном на рис.14.

Графы, деревья - в помощь студенту

Рис.14.

Обозначим ребро, соединяющее вершины Vi и Vj через Xij.

Для удобства использования приведенного выше алгоритма решения поставленной задачи, составим матрицу длин ребер. В рассматриваемом графе количество вершин N=8, следовательно, матрица длин ребер графа GБудет иметь размерность 8×8 и выглядеть следующим образом:

Графы, деревья - в помощь студенту

Согласно приведенному выше алгоритму, выбираем ребро минимальной длины (выбираем среди элементов матрицы C(G), минимальное − это C47=1) и вместе с инцидентными ему двумя вершинами относим к графу G2. Таким образом, Графы, деревья - в помощь студенту. Длина дерева G2 будет равна L(G2)=C47=1. Поскольку Графы, деревья - в помощь студенту, продолжаем работу алгоритма. По четвертой и седьмой строкам ищем минимальное число (за исключением использованной единицы) − ребро минимальной длины, инцидентное либо вершине V4, либо V7. Выбираем ребро X46 с длиной C46=3 и вместе с вершиной V6 добавляем к графу G2, обозначая его теперь как G3: Графы, деревья - в помощь студенту, при этом L(G3)=C47+C46=1+3=4. Аналогично находим графы:

Графы, деревья - в помощь студенту, Графы, деревья - в помощь студенту;

Графы, деревья - в помощь студенту,Графы, деревья - в помощь студенту;

Графы, деревья - в помощь студенту

  • ;
  • ,
  • ;
  • ,
  • .
  • Поскольку I=8=N(G), работа алгоритма заканчивается.

Таким образом, искомое минимальное остовное дерево графа G − граф G8, изображенный на рис. 15, длина которого равна 22.

Рис.15.

Источник: http://matica.org.ua/metodichki-i-knigi-po-matematike/teoriia-grafov/2-5-minimalnoe-ostovnoe-derevo

Теория графов — деревья

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

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

дерево

Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.

Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .

Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.

Пример 1

График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.

Графы, деревья - в помощь студенту

Примечание. Каждое дерево имеет как минимум две вершины первой степени.

Пример 2

Графы, деревья - в помощь студенту

В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.

лес

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

пример

Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.

Графы, деревья - в помощь студенту

Охватывающие деревья

Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –

  • H это дерево
  • H содержит все вершины G.

Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.

пример

Графы, деревья - в помощь студенту

В приведенном выше примере G является связным графом, а H является подграфом G.

Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.

Circuit Rank

Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.

Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.

Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.

Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.

пример

Посмотрите на следующий график –

Графы, деревья - в помощь студенту

Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.

Тогда ранг цепи

G = m – (n – 1)
= 7 – (5 – 1)
= 3

пример

Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».

  • По сумме теоремы о степени вершин
  • n ∑ i = 1 градус (V i ) = 2 | E |
  • 6 × 3 = 2 | E |
  • | E | = 9
  • Схема ранг = | E | – (| V | – 1)
  • = 9 – (6 – 1) = 4

Теорема Кирхгофа

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

пример

Графы, деревья - в помощь студенту

Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».

Источник: https://coderlessons.com/tutorials/akademicheskii/izuchit-teoriiu-grafov/teoriia-grafov-derevia

Дерево

 

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент (корень), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями. Каждый элемент бинарного дерева называется узлом. Связи между узлами дерева называются его ветвями.

Графы, деревья - в помощь студенту

  • A — корень дерева
  • В — корень левого поддерева
  • С — корень правого поддерева

Корень дерева расположен на уровне с минимальным значением.

Узел D, который находится непосредственно под узлом B, называется потомком B. Если D находится на уровне i, то B – на уровне i-1. Узел B называется предком D.

  • Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.
  • Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
  • Остальные элементы – внутренние узлы (узлы ветвления).

Число потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.

Число ветвей, которое нужно пройти от корня к узлу x, называется длиной пути к x. Корень имеет длину пути равную 0; узел на уровне i имеет длину пути равную i.

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

Имеется много задач, которые можно выполнять на дереве.

Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

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

Способы обхода дерева

Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.

Графы, деревья - в помощь студенту

Существует три способа обхода дерева:

  • Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
  • Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
  • Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.

Реализация дерева

  1. Узел дерева можно описать как структуру:
  2. struct tnode {
  3.   int field;           // поле данных
  4.   struct tnode *left;  // левый потомок
  5.   struct tnode *right; // правый потомок
    };
  6. При этом обход дерева в префиксной форме будет иметь вид
  7. void treeprint(tnode *tree) {
  8.   if (tree!=NULL) { //Пока не встретится пустой узел
  9.     cout field; //Отображаем корень дерева
  10.     treeprint(tree->left); //Рекурсивная функция для левого поддерева
  11.     treeprint(tree->right); //Рекурсивная функция для правого поддерева
  12.   }
  13. }
  14. Обход дерева в инфиксной форме будет иметь вид
  15. void treeprint(tnode *tree) {
  16.   if (tree!=NULL) { //Пока не встретится пустой узел
  17.     treeprint(tree->left); //Рекурсивная функция для левого поддерева
  18.     cout field; //Отображаем корень дерева
  19.     treeprint(tree->right); //Рекурсивная функция для правого поддерева
  20.   }
  21. }
  22. Обход дерева в постфиксной форме будет иметь вид
  23. void treeprint(tnode *tree) {
  24.   if (tree!=NULL) { //Пока не встретится пустой узел
  25.     treeprint(tree->left); //Рекурсивная функция для левого поддерева
  26.     treeprint(tree->right); //Рекурсивная функция для правого поддерева
  27.     cout field; //Отображаем корень дерева
  28.   }
  29. }
  30. Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
  • оба поддерева – левое и правое, являются двоичными деревьями поиска;
  • у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X;
  • у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X.
  • Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
  • Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
  • Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Читайте также:  Параллельный перенос и поворот - в помощь студенту

Добавление узлов в дерево

  1. struct tnode * addnode(int x, tnode *tree) {
  2.   if (tree == NULL) { // Если дерева нет, то формируем корень
  3.     tree =new tnode; // память под узел
  4.     tree->field = x;   // поле данных
  5.     tree->left =  NULL;
  6.     tree->right = NULL; // ветви инициализируем пустотой
  7.   }else  if (x < tree->field)   // условие добавление левого потомка
  8.     tree->left = addnode(x,tree->left);
  9.   else    // условие добавление правого потомка
  10.     tree->right = addnode(x,tree->right);
  11.   return(tree);
    }
  12. void freemem(tnode *tree) {
  13.   if(tree!=NULL) {
  14.     freemem(tree->left);
  15.     freemem(tree->right);
  16.     delete tree;
  17.   }
    }
  18. Пример Сортировка элементов массива с помощью дерева
  19. Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.

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

Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.

В дереве каждый узел содержит:

  • указатель на текст слова;
  • счетчик числа встречаемости;
  • указатель на левого потомка;
  • указатель на правого потомка.

Рассмотрим выполнение программы на примере фразы

now is the time for all good men to come to the aid of their party

Графы, деревья - в помощь студенту

Пример реализации

#include
#include
#include
#include
#define MAXWORD 100
struct tnode {                // узел дерева

  •   char *word;                  // указатель на строку (слово)
  •   int count;                   // число вхождений
  •   struct tnode *left;          // левый потомок

  struct tnode *right;         // правый потомок
};

// Функция добавления узла к дереву

struct tnode *addtree(struct tnode *p, char *w) {

  1.   int cond;
  2.   if(p == NULL) {
  3.     p = (struct tnode *)malloc(sizeof(struct tnode));
  4.     p->word = strdup(w);
  5.     p->count = 1;
  6.     p->left = p->right = NULL;
  7.   } else if((cond = strcmp(w, p->word)) == 0)
  8.       p->count++;
  9.   else if(cond < 0)
  10.       p->left = addtree(p->left, w);
  11.   else
  12.      p->right = addtree(p->right, w);
  13.   return p;
    }
  14. // Функция удаления поддерева
  15. void freemem(tnode *tree) {
  16.   if(tree!=NULL) {
  17.       freemem(tree->left);
  18.       freemem(tree->right);
  19.       free(tree);

    }
}

// Функция вывода дерева

void treeprint(struct tnode *p) {

  •   if(p != NULL) {
  •     treeprint(p->left);
  •     printf(«%d %s
    », p->count, p->word);
  •     treeprint(p->right);
  •   struct tnode *root;
  •   char word[MAXWORD];
  •   root = NULL;
  •   do {
  •     scanf(«%s»,word);
  •     if(isalpha(word[0]))
  •       root = addtree(root, word);
  •   }while(word[0]!=‘0’);    // условие выхода – ввод символа ‘0’
  •   treeprint(root);
  •   freemem(root);
  •   getchar();
  •   getchar();
  •   return 0;
    }
  • Результат выполнения
    Графы, деревья - в помощь студенту
    Назад

Назад: Структуры данных

Источник: https://prog-cpp.ru/data-tree/

Дерево целей: как построить и пользоваться

Дерево целей – широко известный термин в менеджменте. Это структурированная, построенная по иерархическому принципу (распределенная по уровням) совокупность целей экономической системы, программы, плана.

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

Что это такое и для чего оно нужно

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

  • Дерево целей имеет стандартную структуру. «Стволом» дерева целей является главная проблема, для которой требуется найти решение.
  • «Ветки» — это задачи второго, третьего, четвёртого и так далее уровней.

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

Графическое изображение задач в таком виде помогает человеку чётко продумать план достижения намеченного. Изобразив свои планы в виде графа, человек видит с какими проблемами он столкнется и какие дополнительные ресурсы ему потребуются, чтобы достичь задуманного.

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

Как построить

Правила, используемые при построении дерева целей, весьма простые:

  1. Вначале определяется главная задача, которую необходимо решить. Она то и будет вершиной или «стволом» дерева. Обычно такую задачу называют генеральной. Она, как правило, не может быть достигнута сразу. Для того чтобы её достичь, необходимо решение других подцелей, результат которых нужен для выполнения генеральной.
    Они, подцели, будут называться «ветвями». Ветвь тоже может иметь подцели.
  2. При построении дерева целей нужно чётко и детально описывать каждую ветвь. Каждая цель также должна иметь нужное количество подцелей, для того чтобы быть реализованной. В итоге должно получиться такое дерево, которое полностью сосуществует решению той или иной проблемы. Оно должно содержать все необходимые шаги и ресурсы для решения главной задачи.

Принципы построения

В менеджменте приняты следующие принципы построения дерева целей:

  • Учитывайте потребности и ресурсы

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

Бывает так, что поставленная задача не может быть решена, потому что не хватает ресурсов для её решения. Или нет возможности оценить наличие ресурсов, так как проблема слишком большая. В этом случае дерево целей хороший вариант для анализа ситуации. Учитывайте потребности и ресурсы, которые есть в вашем распоряжении, при построении дерева целей.

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

  • Разбейте постановку на этапы

Рационально будет ставить задачи в несколько этапов. Первым этапом ставится генеральная цель. Затем для её выполнения ищутся и анализируются ресурсы. После чего, как правило, понадобится поставить подцели. Аналогично для реализации подцелей тоже ищутся ресурсы.

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

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

  • Соответствие структуре предприятия

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

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

Это наиболее удобное построение дерева целей для систем, состоящих из нескольких элементов или предприятий.

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

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

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

Примеры построения

Графы, деревья - в помощь студентуРазберём построение дерева целей на следующих примерах целей: поступление в ВУЗ и финансовое благополучие. Как получить дерево целей?

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

Допустим, главная задача — поступление в ВУЗ. Построение дерева целей для будущего студента требует учесть имеющиеся ресурсы и выделить подцели. Какие могут быть ресурсы для поступления в ВУЗ.

К ресурсам в этом случае относятся:

  1. Образование, полученное в школе;
  2. Финансовые возможности семьи;
  3. Связи.

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

Получаем следующие подцели:

  1. Наладить связи, при возможности;
  2. Взять кредит на обучение или найти источник дополнительного заработка;
  3. Заниматься с репетитором.

В свою очередь, эти цели могут иметь подцели. Рассмотрим на примере цели о занятиях с репетитором. Сюда нужно отнести:

  1. Организация дополнительных доходов, чтобы оплачивать услуги репетитора;
  2. Поиск репетитора обладающего нужными знаниями;
  3. Выделение дополнительного времени на занятия.

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

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

А поступление в заграничный престижный ВУЗ, это уже совсем другое. Тут дополнительно понадобяться и знание языка, и изучение возможностей проживания в другой стране во время учебы, и получение визы и многое другое.

Теперь разберём пример построения графа для создания финансового благополучия.
Начнём строить дерево целей с постановки главного замысла: финансовое благополучие.

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

Источник: https://HeadLife.ru/derevo-celej/

Деревья и лес в теории графов

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

Наличие этих двух свойств (связность и отсутствие циклов) позволяет жестко связать число вершин и число ребер: в дереве с вершинами всегда ребер. Пример графа–дерева приведен на рисунке 3.13. В этом графе 8 вершин и 7 ребер.

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

Графы, деревья - в помощь студентуВершина графа называется концевой или висячей, если В графе на рис. 3.13 концевыми являются вершины .

Неориентированный граф–дерево может быть превращен в ориентированный. Ориентация неориентированного дерева проводится следующим образом.

В дереве выбирается вершина – так называемый корень дерева , и все ребра такого дерева с корнем ориентируются от этой вершины – корня. Для каждой выбранной вершины ориентация дерева единственна, все ребра ориентированы от корня.

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

В каждую вершину ориентированного дерева (за исключением корня) входит только одно ребро. Любое дерево можно ориентировать, выбрав в качестве корня любую его вершину.

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

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

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

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

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

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

В данном примере, в частности, последовательность вершин является тупиковой.

Рис. 3.15. Граф–дерево, соответствующий полному перебору вариантов построения гамильтонового цикла в исходном графе рис. 3.14.

Приведенный на рис. 3.15 граф–дерево построен для решения задачи поиска кратчайшего гамильтонового пути с использованием метода полного перебора вариантов.

Проблема, однако, в том, что при большом числе вершин полный перебор вариантов, это работа, требующая огромных вычислений. В частности, для полного графа с вершинами число маршрутов равно . Если 5!=120, то 10!=3 628 800.

И все-таки перебор маршрутов иногда бывает полезен. Известен метод решения задачи, в соответствии с которым шаг за шагом строится не полное, а «усеченное» дерево – часть ветвей в процессе его «выращивания» отсекаются, а оставшиеся ветви ведут к решению.

Этот метод называется методом ветвей и границ.

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

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

Источник: https://videouroki.net/razrabotki/dieriev-ia-i-lies-v-tieorii-ghrafov.html

Ссылка на основную публикацию