Тема урока: Основные понятия теории графов.

Тема урока: Основные понятия теории графов.    Урок №  Цели урока: 1. Обучающая: Рассмотреть основные понятия теории графов.  2. Развивающая: Способствовать развитию логического мышления, памяти.         3. Воспитательная: Аккуратное ведение конспектов, самодисциплина.    : Урок изучения нового материала          Тип  урока        Вид урока: лекция         Методы:  словесные                 Оборудование: мультимедийный проектор, экран. Ход урока.  I. Оргмомент II. Актуализация опорных знаний      Устный опрос.  II. Целевая установка. 1. Тема урока                      2. Цель урока III. Формирование новых понятий и способов действий.                Графом G = ( V, Х ) называется пара двух конечных множеств:   множество   точек   и   множество   линий, соединяющих некоторые пары точек.  Точки называются вершинами,  или узлами графа. Линии ­ ребрами графа Если ребро графа соединяет две вершины,  то говорят, что это ребро им инцидентно.   Две вершины графа называются смежными,  если имеется инцидентное им ребро. На рисунке А и В, А и С ­ смежные вершины. Два ребра называются смежными, если они  имеют общую вершину.   Если   граф   имеет   ребро,   у   которого   начало   и   конец совпадают, то это ребро называется петлей.   Граф называется полным, если любые его две  вершины соединены одним и только одним ребром.Вершины в графе могут отличаться друг от друга,  тем скольким ребрам они принадлежат. Степенью вершины называется  число  ребер  графа,  которым  принадлежит  эта вершина. Степень обозначается deg (вершина) = числу. Если степень   вершины   равна   нулю,   то   вершина   называется изолированной. Граф, состоящий из изолированных вершин, называется нуль ­ графом. deg (М) = 0, вершина М ­ изолированная Если   степень   вершины   равна   единице,   то   вершина называется висячей.    Вершина называется  , если четной нечетной ее степень ­  число. четное нечетное В графе G (V, Х) сумма степеней всех его вершин ­ число четное, равное удвоенному числу ребер графа.    deg (А) = 1 deg (C) = 4 deg (Д) = 2 deg (F) = 3 Последовательность   ребер,   в   которой   вторая   вершина предыдущего   ребра   совпадает   с   первой   вершиной следующего,   наз.   маршрутом.   Число   ребер   маршрута   наз. длиной маршрута.  Например, |НСДFД| = 4. Если начальная вершина маршрута совпадает с конечной, то такой маршрут наз. замкнутым или циклом.  t, s, p, r ­ цикл длиной 4  r, t, q, s, u ­ цикл длиной 5 t, s, u, r, t, s, p, r ­ цикл длиной 8  p, u ­ цикл длиной 2 t, s, p, r ­ цепь длиной 4  t, s, u, p, s ­ цикл не является цепью В   маршруте   одно   и   то   же   ребро   может   встретиться несколько раз. Если ребро встретилось только один раз, то маршрут наз. цепью. Виды графов Полный граф Полный граф − это граф, в котором любые две вершины соединены ребром. Плоский граф Граф   называется   плоским,   если   на   плоскости   его ребра пересекаются только в вершинах.    Неплоский графОриентированный граф Если все элементы графа G (V; Е ) упорядоченные пары,   то   граф   называется   ориентированным   или оргграфом.   Ориентированный   граф   состоит   из ориентированных ребер, для которых указано какая вершина   является   началом,   а   какая   ­   концом. Ориентированное   ребро   на   рисунке   изображается стрелкой.   Мультиграф − это такой граф, в котором не допускаются петли, но пары вершин                          могут соединяться более чем одним ребром (см. неплоский граф) Униграф − это такой граф, в котором любые две его вершины соединены не более                     чем одним ребром. Псевдограф – это такой граф, в котором имеются  петли и кратные ребра. Способы задания графа. 1. Аналитический 2. Геометрический ­ рисунки, схемы, диаграммы.  3. Табличный – матричный Матрица инцидентности – таблица, связывающая вершины и ребра. Матрица смежности – таблица, связывающая только вершины. Элементами матриц являются нули и единицы.  Если   между   вершинами   есть   связь,   то   в   таблице   в   соответствующую   клетку   ставится   цифра   1,   в противном   случае   ставим   0.   Если   ребро   инцидентно   вершине,   то   ставим   1,   если   нет,   то   0.   Для ориентированного графа: если вершина является началом ребра, то 1, а если концом, то – 1 (минус один). Если при вершине имеется петля, то в соответствующей клетке ставим 1.    Например,   для   графа   изображенного   на рисунке 5 1 0 1 0 6 0 0 0 1 Матрица смежности В 1 0 1 0 А 0 1 1 1 А В С Д С 1 1 0 1 Д 1 0 1 1 Матрица инцидентности 4 1 0 0 1 1 1 1 0 0 А В С Д 2 0 1 1 0 3 0 0 1 1 IV.  Итог  урока.       Подведение итогов, выводы. V. Домашнее задание:           Конспект