Инфоурок Другое ПрезентацииОпределение графа

Определение графа

Скачать материал
Скачать материал "Определение графа"

Получите профессию

Копирайтер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Методические разработки к Вашему уроку:

Получите новую специальность за 3 месяца

Специалист по переработке нефти и газа

Описание презентации по отдельным слайдам:

  • Определение графаФигура, образованная конечным набором точек плоскости и отре...

    1 слайд

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

  • Задача ЭйлераТеория графов зародилась в ходе решения головоломок двести с лиш...

    2 слайд

    Задача Эйлера
    Теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Одной из таких задач-головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).
    Задача. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (Л - левый берег, П - правый берег, А и Б - острова). Можно ли, прогуливаясь вдоль реки, пройти по каждому мосту ровно один раз?

  • Уникурсальные графыНа рисунке представлен граф, соответствующий задаче Эйлера...

    3 слайд

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

  • ТеоремаИндексом вершины графа называется число ребер, сходящихся в этой верши...

    4 слайд

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

  • Решение задачи ЭйлераРешение задачи Эйлера. Найдем индексы  вершин графа зада...

    5 слайд

    Решение задачи Эйлера
    Решение задачи Эйлера. Найдем индексы вершин графа задачи Эйлера. Вершина А имеет индекс 5, Б - 3, П - 3 и Л - 3. Таким образом, мы имеем четыре вершины нечетного индекса, и, следовательно, данный граф не является уникурсальным. Значит, нельзя пройти по каждому из семи мостов только один раз.

  • Вопрос 1Какая фигура называется графом? Ответ: Графом называется фигура, обра...

    6 слайд

    Вопрос 1
    Какая фигура называется графом?
    Ответ: Графом называется фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек.

  • Вопрос 2Какой граф называется уникурсальным? Ответ: Граф называется уникурсал...

    7 слайд

    Вопрос 2
    Какой граф называется уникурсальным?
    Ответ: Граф называется уникурсальным, если его можно ли нарисовать «одним росчерком», т.е. не отрывая карандаша от бумаги и проходя по каждому ребру ровно один раз.

  • Вопрос 3Что называется индексом вершины графа? Ответ: Индексом вершины графа...

    8 слайд

    Вопрос 3
    Что называется индексом вершины графа?
    Ответ: Индексом вершины графа называется число ребер, сходящихся в этой вершине (ребра, с началом и концом в данной вершине считаются дважды).

  • Вопрос 4Что можно сказать об индексах вершин уникурсального графа?Ответ: Для...

    9 слайд

    Вопрос 4
    Что можно сказать об индексах вершин уникурсального графа?
    Ответ: Для уникурсального графа число вершин нечетного индекса равно нулю или двум.

  • Упражнение 1В графе 4 вершин, каждая из которых имеет индекс 3. Сколько у нег...

    10 слайд

    Упражнение 1
    В графе 4 вершин, каждая из которых имеет индекс 3. Сколько у него ребер? Нарисуйте такой граф.
    Ответ: 6.

  • Упражнение 2В графе 5 вершин, каждая из которых имеет индекс 4. Сколько у нег...

    11 слайд

    Упражнение 2
    В графе 5 вершин, каждая из которых имеет индекс 4. Сколько у него ребер? Нарисуйте такой граф.
    Ответ: 10.

  • Упражнение 3Выясните, какие графы, изображенные на рисунке, являются уникурса...

    12 слайд

    Упражнение 3
    Выясните, какие графы, изображенные на рисунке, являются уникурсальными?
    Ответ: а), б), г), д), ж), з).

  • Упражнение 4Может ли граф иметь: а) одну вершину нечетного индекса; б) две ве...

    13 слайд

    Упражнение 4
    Может ли граф иметь: а) одну вершину нечетного индекса; б) две вершины нечетного индекса; в) три вершины нечетного индекса; г) четыре вершины нечетного индекса?
    Ответ: а), в) Нет; б), г) да.

  • Упражнение 5Какое наименьшее число мостов в задаче о кёнигсбергских мостах пр...

    14 слайд

    Упражнение 5
    Какое наименьшее число мостов в задаче о кёнигсбергских мостах придется пройти дважды, чтобы пройти по каждому мосту?
    Ответ: Два.

  • Упражнение 6Можно ли обойти все ребра тетраэдра, пройдя по каждому ребру ровн...

    15 слайд

    Упражнение 6
    Можно ли обойти все ребра тетраэдра, пройдя по каждому ребру ровно один раз?
    Ответ: Нет.

  • Упражнение 7Какое наименьшее число ребер придется пройти дважды, чтобы обойти...

    16 слайд

    Упражнение 7
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра тетраэдра?
    Ответ: Одно.

  • Упражнение 8Какое наименьшее число ребер придется пройти дважды, чтобы обойти...

    17 слайд

    Упражнение 8
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра тетраэдра и вернуться в исходную вершину?
    Ответ: Два.

  • Упражнение 9Можно ли обойти все ребра куба, пройдя по каждому ребру ровно оди...

    18 слайд

    Упражнение 9
    Можно ли обойти все ребра куба, пройдя по каждому ребру ровно один раз?
    Ответ: Нет.

  • Упражнение 10Какое наименьшее число ребер придется пройти дважды, чтобы обойт...

    19 слайд

    Упражнение 10
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра куба?
    Ответ: Три.

  • Упражнение 11Какое наименьшее число ребер придется пройти дважды, чтобы обойт...

    20 слайд

    Упражнение 11
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра куба и вернуться в исходную вершину?
    Ответ: Четыре.

  • Упражнение 12Можно ли обойти все ребра октаэдра, пройдя по каждому ребру ровн...

    21 слайд

    Упражнение 12
    Можно ли обойти все ребра октаэдра, пройдя по каждому ребру ровно один раз?
    Ответ: Да.

  • Упражнение 13Можно ли обойти все ребра икосаэдра, пройдя по каждому ребру ров...

    22 слайд

    Упражнение 13
    Можно ли обойти все ребра икосаэдра, пройдя по каждому ребру ровно один раз?
    Ответ: Нет.

  • Упражнение 14Какое наименьшее число ребер придется пройти дважды, чтобы обойт...

    23 слайд

    Упражнение 14
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра икосаэдра?
    Ответ: Пять.

  • Упражнение 15Какое наименьшее число ребер придется пройти дважды, чтобы обойт...

    24 слайд

    Упражнение 15
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра икосаэдра и вернуться в исходную вершину?
    Ответ: Шесть.

  • Упражнение 16Можно ли обойти все ребра додекаэдра, пройдя по каждому ребру ро...

    25 слайд

    Упражнение 16
    Можно ли обойти все ребра додекаэдра, пройдя по каждому ребру ровно один раз?
    Ответ: Нет.

  • Упражнение 17Какое наименьшее число ребер придется пройти дважды, чтобы обойт...

    26 слайд

    Упражнение 17
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра додекаэдра?
    Ответ: Девять.

  • Упражнение 18Какое наименьшее число ребер придется пройти дважды, чтобы обойт...

    27 слайд

    Упражнение 18
    Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра додекаэдра и вернуться в исходную вершину?
    Ответ: Десять.

  • Упражнение 19Каким правильным многогранникам соответствуют графы, изображенны...

    28 слайд

    Упражнение 19
    Каким правильным многогранникам соответствуют графы, изображенные на рисунке?
    Ответ: а) куб; б) октаэдр; в) додекаэдр; г) икосаэдр.

Получите профессию

Копирайтер

за 6 месяцев

Пройти курс

Рабочие листы
к вашим урокам

Скачать

Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 625 828 материалов в базе

Скачать материал

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 01.11.2020 4049
    • PPTX 288.5 кбайт
    • Оцените материал:
  • Настоящий материал опубликован пользователем Колынюк Елена Владимировна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал
  • Автор материала

    Колынюк Елена Владимировна
    Колынюк Елена Владимировна
    • На сайте: 3 года и 3 месяца
    • Подписчики: 0
    • Всего просмотров: 81964
    • Всего материалов: 220

Ваша скидка на курсы

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

Курс профессиональной переподготовки

Интернет-маркетолог

Интернет-маркетолог

500/1000 ч.

Подать заявку О курсе

Курс профессиональной переподготовки

Руководство электронной службой архивов, библиотек и информационно-библиотечных центров

Начальник отдела (заведующий отделом) архива

600 ч.

9840 руб. 5900 руб.
Подать заявку О курсе

Курс повышения квалификации

Специалист в области охраны труда

72/180 ч.

от 1750 руб. от 1050 руб.
Подать заявку О курсе
  • Сейчас обучается 40 человек из 19 регионов

Курс профессиональной переподготовки

Библиотечно-библиографические и информационные знания в педагогическом процессе

Педагог-библиотекарь

300/600 ч.

от 7900 руб. от 3950 руб.
Подать заявку О курсе
  • Сейчас обучается 458 человек из 66 регионов

Мини-курс

Поиск работы: карьерные ориентиры и мотивы выбора профессии

6 ч.

780 руб. 390 руб.
Подать заявку О курсе

Мини-курс

Архитектура мира: от Крита до Австралии

6 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 31 человек из 19 регионов

Мини-курс

Классики и современники: литературные портреты и психология творчества

4 ч.

780 руб. 390 руб.
Подать заявку О курсе
  • Сейчас обучается 24 человека из 16 регионов