Основные понятия теории графов граф и его свойства примеры графов




НазваниеОсновные понятия теории графов граф и его свойства примеры графов
Дата конвертации23.02.2013
Размер445 b.
ТипЗадача


Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ


Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ



ЗАДАЧА: НАЙТИ КРАЙЧАЙШИЙ ПУТЬ.

  • Решение.

  • Дано:

  • Иа-Иа (О)

  • Винни-Пух (В)

  • Пятачок (П)

  • Кролик (К)

  • Надо:

  • Найти кратчайший путь



РЕШЕНИЕ:



ГРАФЫ

  • Вершины ГРАФА

  • РЕБРА ГРАФА

  • НУЛЕВОЙ ГРАФ НЕПОЛНЫЙ ГРАФ

  • НОЛНЫЙ ГРАФ

  • Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2



ЗАКОНОМЕРНОСТИ

  • СТЕПЕНЬ ВЕРШИНЫ

  • 1) Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

  • 2) Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа.

  • Число нечетных вершин любого графа четно.



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



Путь в графе. Цикл. Путем в графеконец путиЦиклом Эйлеровой линией



Связные графы.

  • Две вершины графа называются связными

  • вершины называются не связными

  • Граф называется связным…

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

  • Мостом НАЗЫВАЕТСЯ



ДЕРЕВЬЯ

  • Деревом НАЗЫВАЕТСЯ

  • Всякое ребро в дереве является мостом. Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

  • Для каждой пары вершин дерева существует единственный путь, их соединяющий.



Изоморфные графы. Плоские ГРАФЫ. изоморфными (одинаковыми)ГРАФАМИ НАЗЫВАЕТСЯ….



Формула ЭЙЛЕРА

  • В-Р+Г=2

  • Ребро графа называется ориентированным ребром…

  • ориентированным графом называется …

  • Степенью выхода вершины

  • Степенью входа вершины…

  • Путем называется

  • Ориентированным циклом называется

  • расстоянием между вершинами графа…



Похожие:

Основные понятия теории графов граф и его свойства примеры графов iconОсновные понятия теории графов
Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых
Основные понятия теории графов граф и его свойства примеры графов iconТеория графов Граф – это средство для наглядного представления состава и структуры системы
Граф, в котором все линии направленные, называется ориентированным графом(орграфом)
Основные понятия теории графов граф и его свойства примеры графов iconИсследование по элективному курсу «начальные понятия теории графов» ученика 9 класса «Б» моу сош №1 подковырова игоря учитель математики папкова мария юрьевна
Проектное исследование по элективному курсу «начальные понятия теории графов» ученика 9 класса «Б» моу сош №1 подковырова игоря учитель...
Основные понятия теории графов граф и его свойства примеры графов iconИзучить теорию «Граф», изучить теорию «Граф»
Вершины и ребра этих графов отвечают соответственно и химическим связям между ними (химия)
Основные понятия теории графов граф и его свойства примеры графов iconТеория графов Теория графов – обширный самостоятельный раздел дискретной математики
...
Основные понятия теории графов граф и его свойства примеры графов iconГрафы состав графа Граф состоит из вершин, связанных линиями
С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений
Основные понятия теории графов граф и его свойства примеры графов iconРешение задач Алгоритм Крускала
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Через город протекает река Преголя. Она делится...
Основные понятия теории графов граф и его свойства примеры графов iconУрока: «Решение комбинаторных задач с помощью графов» Вопросы к уроку. Чем занимается комбинаторика? Что такое граф? Какие задачи относятся к комбинаторным?
Комбинаторика-раздел математики,рассматривающий вопросы(задачи), связанные с подсчётом числа всевозможных комбинаций из элементов...
Основные понятия теории графов граф и его свойства примеры графов iconВведение в теорию графов

Основные понятия теории графов граф и его свойства примеры графов iconПрименение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям
Создать мотивационную базу для изучения самого молодого раздела современной математики; познакомиться с интенсивно развивающимся...
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница