Презентация Графы. Элементы графов. Виды графов и операции над ними онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Графы. Элементы графов. Виды графов и операции над ними абсолютно бесплатно. Урок-презентация на эту тему содержит всего 46 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Математика » Графы. Элементы графов. Виды графов и операции над ними
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:46 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:644.68 kB
- Просмотров:145
- Скачиваний:4
- Автор:неизвестен
Слайды и текст к этой презентации:
№3 слайд
Содержание слайда: Теория графов представляет собой раздел математики, имеющий широкие практические приложения.
Теория графов представляет собой раздел математики, имеющий широкие практические приложения.
Теория графов – область дискретной математики, особенностью которой является геометрический подход к изучению объектов.
№4 слайд
Содержание слайда: История возникновения графов
Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик) , в которых он описывал решение головоломок и математических развлекательных задач.
Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.
№8 слайд
Содержание слайда: Состав графа
Граф состоит из вершин, связанных линиями. Вершины графа обозначают латинскими буквами A, B, C, D или цифрами.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.
№14 слайд
Содержание слайда: Рёбра, которые начинаются в одной и той же вершине, заканчиваются также в одной и той же вершине, называются кратными, или параллельными.
Рёбра, которые начинаются в одной и той же вершине, заканчиваются также в одной и той же вершине, называются кратными, или параллельными.
Количество одинаковых пар вида называется кратностью ребра
Число рёбер, инцидентных вершине А, называется степенью этой вершины и обозначается (от англ. degree – степень).
№15 слайд
Содержание слайда: На рисунке кратными являются, например, рёбра х1(А, В), х2(А, В). Вершинам А и С инцидентны рёбра х3, х4, х5. Следовательно, ребро АС имеет кратность, равную 3, а ребро АВ – кратность, равную 2.
На рисунке кратными являются, например, рёбра х1(А, В), х2(А, В). Вершинам А и С инцидентны рёбра х3, х4, х5. Следовательно, ребро АС имеет кратность, равную 3, а ребро АВ – кратность, равную 2.
№17 слайд
Содержание слайда: Вершина графа, имеющая степень, равную нулю, называется изолированной.
Вершина графа, имеющая степень, равную нулю, называется изолированной.
Граф, состоящий из изолированных вершин, называется нуль-графом.
Вершина графа, имеющая степень, равную 1, называется висячей.
Граф, не имеющий ребер (дуг), называется пустым.
На рисунке вершина
Е – изолированная:
deg(E)=0.
№19 слайд
Содержание слайда: Теорема 1. В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа:
Теорема 1. В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа:
Количество ребер в любом графе равно половине суммы степеней его вершин.
где - число вершин;
- число рёбер графа.
№22 слайд
Содержание слайда: Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.
Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.
Следствие. Невозможно начертить граф с нечётным числом нечётных вершин.
Граф G называется полным,
если любые две его различные
вершины соединены одним и
только одним ребром.
№24 слайд
Содержание слайда: Дополнением графа называется граф с теми же вершинами V, что и граф G, и имеющий те и только те рёбра , которые необходимо добавить к графу G, чтобы он стал полным. На рисунке дополнением графа G1 до графа G является граф
Дополнением графа называется граф с теми же вершинами V, что и граф G, и имеющий те и только те рёбра , которые необходимо добавить к графу G, чтобы он стал полным. На рисунке дополнением графа G1 до графа G является граф
№27 слайд
Содержание слайда: Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
№29 слайд
Содержание слайда: Пути и маршруты в графах
Путем в ориентированном графе называется последовательность дуг, в которой конечная вершина любой дуги, отличной от последней, является начальной вершиной следующей дуги.
Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути.
Путь, в котором каждая вершина используется не более одного раза, называется простым путем.
Длиной пути в графе называется количество дуг (ребер), составляющих этот путь.
№30 слайд
Содержание слайда: В качестве примера рассмотрим орграф, представленный на рисунке. Одним из существующих путей, соединяющих вершины 1 и 3, является последовательность вершин 1, 2, 1, 4, 3. Единственным простым путем для той же пары вершин является последовательность 1, 4, 3. Пути из вершины 1 в вершину 5 для того же графа не существует.
В качестве примера рассмотрим орграф, представленный на рисунке. Одним из существующих путей, соединяющих вершины 1 и 3, является последовательность вершин 1, 2, 1, 4, 3. Единственным простым путем для той же пары вершин является последовательность 1, 4, 3. Пути из вершины 1 в вершину 5 для того же графа не существует.
№31 слайд
Содержание слайда: Неориентированный граф называется связным, если существует хотя бы один путь между каждой парой вершин.
Неориентированный граф называется связным, если существует хотя бы один путь между каждой парой вершин.
Орграф называется связным, если связен неориентированный граф, который получается из исходного ориентированного заменой всех дуг на ребра.
№32 слайд
Содержание слайда: Путь называется замкнутым, если начальная и конечная вершины совпадают.
Путь называется замкнутым, если начальная и конечная вершины совпадают.
Замкнутый путь называется циклом, если все его вершины (кроме начальной и конечной) различны.
Рассмотрим граф. Для него путь 2, 1, 6, 5, 4, 1, 2 является замкнутым; а путь 1, 6, 5, 4, 1 является циклом.
№33 слайд
Содержание слайда: Последовательность попарно смежных вершин неориентированного графа, т.е. последовательность рёбер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом.
Последовательность попарно смежных вершин неориентированного графа, т.е. последовательность рёбер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом.
Число рёбер маршрута называется длиной маршрута.
Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом.
№34 слайд
Содержание слайда: На рисунке HCDFD – маршрут длиной 4. Обозначение: |HCDFD|=4. Маршрут принято задавать как последовательность рёбер, поскольку это удобно при наличии кратных рёбер.
На рисунке HCDFD – маршрут длиной 4. Обозначение: |HCDFD|=4. Маршрут принято задавать как последовательность рёбер, поскольку это удобно при наличии кратных рёбер.
№35 слайд
Содержание слайда: В графе на рисунке (t, s, p, r), (u, s, t, r) – циклы длиной 4, (r, t, q, s, u) – цикл длиной 5, (t, s, u, r, t, s, p, r) – 8-цикл, (p, u) – 2-цикл, петля (q) – 1-цикл.
В графе на рисунке (t, s, p, r), (u, s, t, r) – циклы длиной 4, (r, t, q, s, u) – цикл длиной 5, (t, s, u, r, t, s, p, r) – 8-цикл, (p, u) – 2-цикл, петля (q) – 1-цикл.
№36 слайд
Содержание слайда: Операции над графами
Одноместные операции
1. Удаление ребра графа — при этом все вершины графа сохраняются
2. Добавление ребра графа между двумя существующими вершинами.
3. Удаление вершины (вместе с инцидентными ребрами).
4. Добавление вершины (которую можно соединить с некоторыми вершинами графа).
5. Стягивание ребра — отождествление пары вершин, т.е. удаление пары смежных вершин, и добавление новой вершины, смежной с теми вершинами, которые были смежны, хотя бы одной из удаленных вершин)
6. Подразбиение ребра с- удаление ребра и добавление новой вершины, которая соединяется ребром с каждой из вершин удаленного ребра.
№37 слайд
Содержание слайда: Операции над графами
Двуместные операции
Объединением графов и называется граф , множество вершин которого , а множество рёбер .
Пересечением графов и называется граф , для которого - множество рёбер, а - множество вершин.
Кольцевой суммой двух графов называется граф , порождённый множеством вершин и множеством рёбер , т.е. множеством рёбер, содержащихся либо в , либо в
, но не в .
№41 слайд
Содержание слайда: Использует графы и дворянство.
Использует графы и дворянство.
На рисунке приведена часть генеалогического дерева знаменитого дворянского рода Л. Н. Толстого. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.
№45 слайд
Содержание слайда: Выводы
Графы – это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используются при составлении карт и генеалогических древ.
В математике даже есть специальный раздел, который так и называется: «Теория графов».
Скачать все slide презентации Графы. Элементы графов. Виды графов и операции над ними одним архивом:
-
Линейная алгебра. Матрицы и операции над ними
-
Комплексные числа и операции над ними
-
Множества и операции над ними (9 класс)
-
Элементы и множества. Операции над множествами и их свойства
-
Высказывания и операции над ними
-
Матрицы и операции над ними
-
Множеества и операции над ними
-
Алгебра высказываний. Высказывания и операции над ними
-
Комплeксные числа. Арифметические операции над ними (10 класс)
-
Курсовая работа по теме Натуральные (целая часть числитель / знаменатель) дроби и операции над ними