Что такое ребра квадрата
Куб и квадрат – разница и отличие между квадратом и кубом
Отличие куба от квадрата, разница между ними
Куб и квадрат часто путают, думая, что это тождественные геометрические фигуры. В действительности они отличаются друг от друга, ведь у каждого из этих объектов имеются только им присущие признаки. Какие, нетрудно понять, зная определение куба и квадрата.
Что такое квадрат и что такое куб
Фото: Квадрат
Квадрат – фигура, лежащая на плоскости, и она двухмерная. Её можно отобразить в виде прямоугольника с идентичными по длине сторонами. Квадрат можно вырезать из бумаги.
Фото: Куб
Куб же является трехмерным объектом, имеющим объём и 12 одинаковых граней. Таким образом, это правильный многогранник. Если разложить его на плоскости, то он будет состоять из 6 квадратов. Для наглядности куб можно склеить из плотной бумаги, а лучше слепить из гипса, пластилина.
Фото: разложенный куб на плоскости
В чем разница между кубом и квадратом: сравнение двух фигур
По сравнению с квадратом, куб – более сложная геометрия. Квадрат является фигурой простой, в нём только 4 стороны и 4 угла, между которыми абсолютное равенство. Квадрат можно назвать подвидом прямоугольника, только у которого ширина и длина сторон одинаковы. При этом квадрат всегда плоский. Чтобы посчитать площадь квадрата, достаточно умножить одну его сторону на другую.
Конфигурация куба сложнее, поскольку в нём уже присутствует третья мера – объём. Эта характеристика отражает пространство, которое занимает объект, в нашем случае куб. У куба также есть и третье измерение (параметр) – высота. Между собой ширина, длина и высота у куба равны.
Нахождение объема и площади
Если необходимо посчитать объем фигуры, то для расчета берут длину любого ребра между гранями и возводят её в третью степень. Для нахождения площади трехмерной фигуры куба надо узнать сумму площади всех его сторон. Поскольку они идентичны, то просто площадь одной стороны умножаем на 6. А чтобы найти площадь одной из сторон, умножаем длину ребра на себя же. Допустим, длина ребра 4 см, чтобы найти площадь одной стороны куба, 4 умножаем на 4 – получаем 16. И эту цифру уже увеличиваем в 6 раз. Значит, объём куба будет равен 96 см²
Сложные свойства куба
По сравнению с квадратом куб обладает более сложными, дополнительными характеристиками. Например, геометрический объект имеет четыре сечения, которые представляют собой правильные шестиугольники. Все сечения куба проходят через его центр и располагаются перпендикулярно относительно четырех главных его диагоналей.
Поскольку куб имеет объём, то в него можно вписать различные многогранники – такие как тетраэдр (простейший многогранник с гранями в виде 4-х треугольников), октаэдр (у этого многогранника уже 8 граней), икосаэдр (20 граней многогранника).
Чтобы ещё легче было понять разницу между кубом и квадратом, имеет смысл оценить свойства каждой фигуры наглядно. К примеру, взять обычный детский кубик с наклеенными картинками на его стороны. Так вот, сам кубик – это фигура куб, а каждая наклеенная на его сторону картинка – квадрат.
Прямоугольный параллелепипед. Что это такое?
Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).
Определение параллелепипеда
Начнем с того, что узнаем, что такое параллелепипед.
Параллелепипедом называется призма, основаниями которой являются параллелограммы. Другими словами, параллелепипед — это многогранник с шестью гранями. Каждая грань — параллелограмм.
На рисунке два параллелограмма АВСD и A1B1C1D1. Основания параллелепипеда, расположены параллельно друг другу в плоскостях. А боковые ребра АA1, ВB1, CC1, DD1 параллельны друг другу. Образовавшаяся фигура — параллелепипед.
Внимательно рассмотрите, как выглядит параллелепипед и каковы его составляющие.
Когда пересекаются три пары параллельных плоскостей, образовывается параллелепипед.
Основанием параллелепипеда является, в зависимости от его типа: параллелограмм, прямоугольник, квадрат.
Параллелепипед — это:
Правильный параллелепипед на то и правильный, что два его измерения равны. Две грани такого правильного параллелепипеда — квадраты.
Свойства параллелепипеда
Быть параллелепипедом ー значит неотступно следовать законам геометрии. Иначе можно скатиться до простого параллелограмма.
Вот 4 свойства параллелепипеда, которые необходимо запомнить:
Прямой параллелепипед
Прямой параллелепипед — это параллелепипед, у которого боковые ребра перпендикулярны основанию.
Основание прямого параллелепипеда — параллелограмм. В прямом параллелепипеде боковые грани — прямоугольники.
Свойства прямого параллелепипеда:
На слух все достаточно занудно и сложно, но на деле все свойства просто описывают фигуру. Внимательно прочтите вслух каждое свойство, разглядывая рисунок параллелепипеда после каждого пункта. Все сразу встанет на места.
Формулы прямого параллелепипеда:
Прямоугольный параллелепипед
Определение прямоугольного параллелепипеда:
Прямоугольным параллелепипедом называется параллелепипед, у которого основание — прямоугольник, а боковые ребра перпендикулярны основанию.
Внимательно рассмотрите, как выглядит прямоугольный параллелепипед. Отметьте разницу с прямым параллелепипедом.
Свойства прямоугольного параллелепипеда
Прямоугольный параллелепипед обладает всеми свойствами произвольного параллелепипеда.
Формулы прямоугольного параллелепипеда:
Диагонали прямоугольного параллелепипеда: теорема
Не достаточно просто знать свойства прямоугольного параллелепипеда, нужно уметь их доказывать.
Если есть теорема, нужно ее доказать. (с) Пифагор
Теорема: Квадрат диагонали прямоугольного параллелепипеда равен сумме квадратов трех его измерений.
В данном случае, три измерения — это длина, ширина, высота. Длина, ширина и высота — это длины трех ребер, исходящих из одной вершины прямоугольного параллелепипеда.
Дан прямоугольный параллелепипед ABCDA1B1C1D1. Доказать теорему.
Доказательство теоремы:
Чтобы найти диагональ прямоугольного параллелепипеда, помните, что диагональ — это отрезок, соединяющий противоположные вершины.
Все грани прямоугольного параллелепипеда — прямоугольники.
ΔABD: ∠BAD = 90°, по теореме Пифагора
ΔB₁BD: ∠B₁BD = 90°, по теореме Пифагора
d² = a² + b² + c²
Доказанная теорема — пространственная теорема Пифагора.
У нас есть отличные дополнительные онлайн занятия по математике для учеников с 1 по 11 классы, записывайся!
Куб: определение, свойства и формулы
Кубом называется прямоугольный параллелепипед, все три измерения которого равны.
Каждая грань куба — это квадрат.
Свойства куба:
Помимо основных свойств, куб характеризуется умением вписывать в себя тетраэдр и правильный шестиугольник.
Формулы куба:
Решение задач
Чтобы считать тему прямоугольного параллелепипеда раскрытой, стоит потренироваться в решении задач. 10 класс — время настоящей геометрии для взрослых. Поэтому, чем больше практики, тем лучше. Разберем несколько примеров.
Задачка 1. Дан прямоугольный параллелепипед. Нужно найти сумму длин всех ребер параллелепипеда и площадь его поверхности.
Формула нахождения площади поверхности параллелепипеда Sп.п = 2(ab+bc+ac).
Тогда: S = (5*8 + 8*10 + 5*10) * 2 = 340 см2.
Задачка 2. Дан прямоугольный параллелепипед АВСDA1B1C1D1.
Нужно найти длину ребра A1B1.
В фокусе внимания треугольник BDD1.
Угол D = 90°. Против равных сторон лежат равные углы.
Задачка 3. Дан прямоугольный параллелепипед АВСDA1B1C1D1.
AB = 4
AD = 6
AA1= 5
Нужно найти отрезок BD1.
В треугольнике ADB угол A = 90°.
По теореме Пифагора:
BD 2 = AB 2 +AD 2
BD 2 = 4 2 + 6 2 = 16 + 36 = 52
В треугольнике BDD1 угол D = 90°.
BD1 2 = 52 + 25 = 77.
Самопроверка
Теперь потренируйтесь самостоятельно — мы верим, что все получится!
Задачка 1. Дан прямоугольный параллелепипед. Измерения (длина, ширина, высота) = 8, 10, 20. Найдите диагональ параллелепипеда.
Подсказка: если нужно выяснить, чему равна диагональ прямоугольного параллелепипеда, вспоминайте теорему.
Задачка 2. Дан прямоугольный параллелепипед АВСDA1B1C1D1.
Вычислите длину ребра AA1.
Как видите, самое страшное в параллелепипеде — 14 букв в названии. Чтобы не перепутать прямой параллелепипед с прямоугольным, а ребро параллелепипеда с длиной диагонали параллелепипеда, вот список основных понятий:
Что такое куб: определение, свойства, формулы
В публикации мы рассмотрим определение и основные свойства куба, а также формулы, касающиеся данной геометрической фигуры (расчет площади поверхности, периметра ребер, объема, радиуса описанного/вписанного шара и т.д.).
Определение куба
Куб – это правильный многогранник, все грани которого являются квадратами.
Примечание: куб является частным случаем параллелепипеда или призмы.
Свойства куба
Свойство 1
Как следует из определения, все ребра и грани куба равны. Также противоположные грани фигуры попарно параллельны, т.е.:
Свойство 2
Диагонали куба (их всего 4) равны и в точке пересечения делятся пополам.
Свойство 3
Все двугранные углы куба (углы между двумя гранями) равны 90°, т.е. являются прямыми.
Например, на рисунке выше угол между гранями ABCD и AA1B1B является прямым.
Формулы для куба
Примем следующие обозначения, которые будут использоваться далее:
Диагональ
Длина диагонали куба равняется длине его ребра, умноженной на квадратный корень из трех.
Диагональ грани
Диагональ грани куба равна его ребру, умноженному на квадратный корень из двух.
Площадь полной поверхности
Площадь полной поверхности куба равняется шести площадям его грани. В формуле может использоваться длина ребра или диагонали.
Периметр ребер
Периметр куба равен длине его ребра, умноженной на 12. Также может рассчитываться через диагональ.
Объем
Объем куба равен длине его ребра, возведенной в куб.
Радиус описанного вокруг шара
Радиус шара, описанного около куба, равняется половине его диагонали.
Радиус вписанного шара
Радиус вписанного в куб шара равен половине длины его ребра.
Математика. 5 класс
Конспект урока
Перечень рассматриваемых вопросов:
Прямоугольный параллелепипед – это шестигранник, у которого все грани являются прямоугольниками.
Грань – плоская поверхность предмета, составляющая угол с другой такой же поверхностью.
Основания параллелепипеда – это его верхняя и нижняя грани.
Никольский С. М. Математика. 5 класс. Учебник для общеобразовательных учреждений.// С. М. Никольский, М. К. Потапов, Н. Н. Решетников и др. – М.: Просвещение, 2017. – 272 с.
1. Чулков П. В. Математика: тематические тесты. 5 класс.// П. В. Чулков, Е. Ф. Шершнёв, О. Ф. Зарапина. – М.: Просвещение, 2009. – 142 с.
2. Шарыгин И. Ф. Задачи на смекалку: 5-6 класс. // И. Ф. Шарыгин, А. В. Шевкин. – М.: Просвещение, 2014. – 95 с.
Теоретический материал для самостоятельного изучения
Мир, в котором мы живём, состоит из огромного количества разных по форме, цвету и размеру предметов. Изучая их свойства, люди открывают что-то новое. Например, математики в окружающем пространстве обращают внимание на геометрические тела: цилиндры, кубы и так далее.
Сегодня мы рассмотрим прямоугольный параллелепипед – многогранник, название которого с древнегреческого переводится как «идущие рядом плоскости».
Прямоугольный параллелепипед ограничен шестью прямоугольниками, то есть шестью гранями. Грань, на которую поставлен параллелепипед, и ей противоположную называют нижним и верхним основаниями.
Остальные четыре грани называют боковыми гранями.
Стороны граней параллелепипеда называют рёбрами. Их двенадцать.
Концы рёбер называют вершинами. Их в параллелепипеде восемь.
Каждая вершина является общим концом трёх рёбер.
Длины двух рёбер основания, выходящих из одной вершины, называют длиной и шириной прямоугольного параллелепипеда.
Длину бокового ребра называют высотой.
Таким образом, длины трёх рёбер, выходящих из одной вершины, называют длиной, шириной, высотой. Иначе длину, ширину и высоту называют измерениями прямоугольного параллелепипеда.
Прямоугольный параллелепипед, у которого три ребра, выходящие из одной вершины, равны между собой, называется кубом. Каждая грань куба – квадрат.
Рассмотрим свойства прямоугольного параллелепипеда и куба.
У прямоугольного параллелепипеда противоположные грани равны.
Все грани куба равны между собой.
Построим прямоугольник заданной длины а и высоты h.
Для этого от каждой вершины отложим отрезок, равный половине ширины b под углом 45 градусов. И соединим концы отрезков, причём невидимые грани – пунктирной линией.
Изготовить параллелепипед можно несколькими способами. Например, с помощью развёртки. Для этого на бумаге вычерчивается макет, который выглядит как приведённый шаблон. Обратите внимание, что на картинке даны припуски для того, чтобы можно было склеить параллелепипед.
Другой способ изготовления параллелепипеда – модульная сборка. Она требует ряда последовательных действий.
1) Вырежьте из бумаги шесть одинаковых квадратов.
2) Согните их к середине, как показано на картинке.
3) Согните верхние и нижние края заготовки, как показано на рисунке.
4) Верхний уголок опустите вниз, а нижний – загните наверх. После этого получится квадрат.
5) Сделайте шесть таких заготовок и соедините их в один параллелепипед. Для этого каждый острый уголок вставьте в кармашек соседней части кубика.
№ 1. Какова площадь верхней грани параллелепипеда?
Решение: площадь верхней грани параллелепипеда соответствует площади прямоугольника. Верхняя грань параллелепипеда имеет длину 15см и ширину 3см. Значит, далее по формуле вычисляем площадь:
S = а ·b = 15 см · 3 см = 45 см 2
Ответ: 45 см 2
№ 2. На рисунке изображен куб, состоящий из нескольких маленьких кубиков. Сколько маленьких кубиков ушло на построение данного куба?
Решение: для решения задачи нужно посмотреть, сколько маленьких кубиков расположено на одной грани куба. Их 9 штук. Всего на рисунке изображено три грани. Таким образом, чтобы найти общее количество маленьких кубиков, следует умножить количество кубиков, умещающихся на одной грани, на количество граней: 9 · 3= 27 штук.
Теория графов. Основные понятия и виды графов
Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).
Теория графов
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Давайте на примере.
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
В данном случае точки — это вершины графа, а связки — рёбра графа.
Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.
Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.
Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.
Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.
Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.
Основные понятия теории графов
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Доказательство леммы о рукопожатиях
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.
Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.
Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
Путь и цепь в графе
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Два графа называются изоморфными, если у них поровну вершин. При этом вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие занумерованные теми же числами вершины второго графа.
Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.
Визуализация графовых моделей
Визуализация — это процесс преобразования больших и сложных видов абстрактной информации в интуитивно-понятную визуальную форму. Другими словами, когда мы рисуем то, что нам непонятно — и сразу все встает на свои места.
Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.
Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.
Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.
Виды изобразительных соглашений:
Виды графов
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированные и неориентированные графы
Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.
Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы
Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».
Смешанным называют граф, в котором есть ребра хотя бы двух из упомянутых трех разновидностей (звенья, дуги, петли).
Пустой граф — это тот, что состоит только из голых вершин.
Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.
Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.
Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.
Двудольный граф
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.
Эйлеров граф
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?
Регулярный граф
Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.
Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.
Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.
Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.
Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:
Гамильтонов граф
Гамильтоновым графом называется граф, содержащий гамильтонов цикл.
Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.
Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.
Определение дерева
Деревом называется связный граф, который не содержит циклов.
Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.
Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.
Простым путем называется путь, в котором никакое ребро не встречается дважды.
Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:
Дерево — минимальный по числу рёбер связный граф.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Определения дерева:
Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.
Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.
Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:
Теоремы дерева и их доказательства
В дереве с более чем одной вершиной есть висячая вершина.
Доказательство первой теоремы:
Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.
Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.
В дереве число вершин на 1 больше числа ребер.
Доказательство второй теоремы:
Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n
