Дискретная математика реферат деревья

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

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

Соглашение об использовании материалов сайта

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Подобные документы

Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.

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

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

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

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

Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.

Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.

Источник

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

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

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

Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку «Скачать архив»

Подобные документы

Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.

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

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

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

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

Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.

Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.

Источник

Деревья

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

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

Описание деревьев

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

Теорема.Для графа G следующие утверждения эквивалентны:

(2) любые две вершины в G соединены единственной простой цепью;

(3) G — связный граф и p=q+1;

(4) G — ациклический граф и p=q+1;

(5) G — ациклический граф, и если любую пару несмежных вершин

соединить ребром х, то в графе G + x будет точно один простой цикл;

(6) G — связный граф, отличный от Кр для р>=З, и если любую пару несмежных вершин соединить ребром х, то в графе G + x будет точно один простой цикл;

(7) G — граф, отличный от КзUК1 и КзUК2, p=q+1, и если любую пару несмежных вершин соединить ребром х, то в графе G + x будетточно один простой цикл.

Доказательство.(1) влечет (2). Поскольку G — связный граф, то любые две его вершины соединены простой цепью. Пусть Р1 и P2— две различные простые цепи, соединяющие вершины и и v, и пусть w — первая вершина, принадлежащая Р2 (при переходе по P1 из и в v), такая, что w принадлежит и P1 и Р2, но вершина, предшествующая ей в P1, не принадлежит Р2. Если w’ — следующая за w вершина в Р1 принадлежащая также Р2, то сегменты (части) цепей P1 и Р2, находящиеся между вершинами w и w’, образуют простой цикл в графе G. Поэтому, если G — ациклический граф, то между любыми двумя его вершинами существует самое большее одна простая цепь.

(2) влечет (3). Ясно, что граф G — связный. Соотношение р =q+1 докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше р вершин. Если же граф G имеет р вершин, то удаление из него любого ребра делает граф G несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе G должно равняться р — 1.

(3) влечет (4). Предположим, что в графе G есть простой цикл длины п. Этот цикл содержит nвершин иnребер, а для любой из р —nвершин, не принадлежащих циклу, существует инцидентное ей ребро, которое лежит на геодезической, идущей от некоторой вершины цикла. Все такие ребра попарно различны; отсюда q>p, т. е. пришли к противоречию.

(4) влечет (5). Так как G — ациклический граф, то каждая его компонента является деревом. Если всего k компонент, то, поскольку в каждой из них число вершин на единицу больше числа ребер, имеем p = q + k. В нашем случае должно быть k=1, так что G — связный граф. Таким образом, G — дерево и любые две его вершины соединяет простая единственная цепь. Если к дереву G добавить ребро uv, то ребро вместе с единственной простой цепью, соединяющей вершины uи v, образует простой цикл, который также единствен в силу единственности простой цепи.

(5) влечет (6). Поскольку каждый полный граф КР для р>3 содержит простой цикл, граф G не может быть одним из этих графов. Граф G должен быть связным, так как в ином случае можно было бы добавить ребро х, соединяющее две вершины из разных компонент графа G, и граф G + x был бы ациклическим.

(6) влечет (7). Докажем, что любые две вершины графа G соединены единственной простой цепью, а тогда, поскольку (2) влечет (3), получим p=q+1. Ясно, что в графе G любые две вершины соединены простой цепью. Если какая-то пара вершин графа G соединена двумя простыми цепями, то из доказательства того, что (1) влечет (2), следует наличие у графа G простого цикла Z. В Z не может быть более трех вершин, так как иначе, соединив ребром х две несмежные вершины в Z, получим граф G + x, имеющий более одного простого цикла (если же в Z нет несмежных вершин, то в графе G более одного цикла). Таким образом, цикл Z есть К.3, и он должен быть собственным подграфом графа G, поскольку по предположению G не является полным графом КР с р>3. Так как G — связный граф, то можно предположить, что в G есть другая вершина, смежная с некоторой вершиной подграфа К3. Тогда ясно, что если к графу G добавлять ребро, то его можно добавить так, чтобы в графе G + x образовались, по крайней мере два простых цикла. Если больше нельзя добавить новых ребер, не нарушая для графа G второго условия из (6), то G есть КР с р>3 вопреки предположению.

(7) влечет (1). Если граф G имеет простой цикл, то этот цикл должен быть треугольником, являющимся компонентой графа G, что было показано в предыдущем абзаце. В этой компоненте соответственно три вершины и три ребра. Все остальные компоненты графа G должны быть деревьями, но для того, чтобы выполнялось соотношение p = q + l, должно быть не более одной компоненты, отличной от указанного треугольника. Если это дерево содержит простую цепь длины 2, то к графу G можно так добавить ребро х, чтобы образовать в графе G + x два простых цикла. Следовательно, этим деревом может быть или К1 или K2. Значит, граф G — или Кз U K₁или К₃U К₂, а эти графы мы исключили из рассмотрения. Таким образом, G- ациклический граф. Но если G — ациклический граф и p=q+1, то G связен, поскольку (4) влечет (5), а (5) влечет (6). Итак,

G -дерево, и теорема доказана.

Так как для нетривиального дерева di = 2q=2(p— 1), то в дереве должно быть, по крайней мере, две вершины со степенями, меньшими 2.

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

Этот результат также следует из теоремы.

Источник