Граф и его элементы

Разделы: Математика

Ключевые слова: графы

Дисциплина: Дискретная математика.

Цели занятия:

  • Обучающая - сформировать представление о графе, способах его задания и его основных элементах.
  • Развивающая - развивать умение выделять главное; развивать умение учащихся оперировать понятиями; развивать логическое мышление учащихся.
  • Воспитательная - продолжить формирование логического мышления; способствовать развитию познавательного интереса к предмету.

Оборудование: ПК, проектор, экран.

План занятия

Содержание этапов урока

Виды и формы работы

I. Организационный момент.

Приветствие, проверка личного состава - 5 мин

II. Проверка домашнего задания.

Письменный фронтальный опрос (тест) - 10 мин

III. Мотивационное начало урока.

Постановка проблемы - 5 мин

IV. Объяснение нового материала.

Использование подготовленной презентации. Решение проблемы

V. Этап общения, систематизации знаний и закрепление изученного.

Решение задач по карточкам.

VI. Подведение итогов.

Выставление оценок. Домашнее задание. Рефлексия.

Ход занятия

I. Организационный момент

Приветствие учащихся. Проверка личного состава.

II. Проверка домашнего задания

Фронтальный письменный опрос (тестирование)

III. Мотивационное начало урока

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

Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам. С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями - пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо - граф.

Графы служат удобным средством описания связей между объектами. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда от пункта А до пункта Б.

IV. Объяснение нового материала

Определение 1: Графом G = (v, x) называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек.

Точки называются вершинами, или узлами, графа, линии - ребрами графа.

Если ребро графа соединяет две его вершины, то говорят, что это ребро им инцидентно.

Определение 2: Две вершины графа называются смежными, если существует инцидентное им ребро.

Определение 3: Два ребра называются смежными, если они имеют общую вершину.

Определение 4: Если граф имеет ребро, у которого начало и конец совпадают, то это ребро называется петлей (у графа петля - q(C,C)).

Определение 5: Ребра, соединяющие одни и те же вершины, называются кратными (или параллельными) ребрами.

Определение 6: Количество кратных ребер (u, v) называется кратностью ребра (u, v).

Определение 7: Число ребер, инцидентных вершине a, называется степенью этой вершины и обозначается deg(a). Если вершине инцидентна петля, она дает вклад в степень, равный двум, так как оба конца приходят в эту вершину.

Определение 8: Граф называется полным, если любые две его различные вершины соединены одним и только одним ребром.

Определение 9: Дополнением графа называется граф с теми же вершинами и имеющий те и только те ребра, которые необходимо добавить к исходному графу, чтобы он стал полным.

Определение 10: Если в графе G указано направление ребер, то граф называется ориентированным.

Ребра ориентированного графа называются дугами.

Определение 11: Если направление ребер не указано, то граф называется неориентированным (н-графом) или просто графом.

Существует несколько способов задания графов:

1. Перечисление (список) ребер графа и вершин графа.

2. В виде геометрического объекта .

3. Матричный способ

а) матрица смежности А;

б) матрица инцидентности В.

Определение 12: Назовем матрицей инцидентности таблицу , состоящую из n строк (вершины) и m столбцов (ребра), в которой:

для неориентированного графа:

bij = 1, если вершина Vi инцидентна ребру ji,

bij=0, если вершина Vi не инцидентна ребру Xj,

для ориентированного графа:

bij = 1, если вершина Vi является началом дуги Xj,

bij = 0, если вершина Vi не инцидентна дуге Xj,

bij = -l, если вершина Vi является концом дуги Xj.

Матрицей смежности графа g(v,x) без кратных ребер называют квадратную матрицу a порядка N, в которой:

V. Этап общения, систематизации знаний и закрепление изученного

1. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

2. Задайте следующий орграф матрицей инцидентности

    3. Задайте следующий граф матрицей смежности

    Задания для самостоятельного решения

    1. Пусть орграф задан матрицей смежности. Постройте изображение этого графа, укажите степени вершин графа. По матрице смежности постройте матрицу инцидентности этого графа:

    2. Граф G задан диаграммой (рис. 2.27).

    1. Составьте для него матрицу смежности.
    2. Постройте матрицу инцидентности.
    3. Укажите степени вершин графа.

    VI. Подведение итогов

    1. Что называется графом?
    2. Ориентированный граф?
    3. Неориентированный граф?
    4. Какие элементы графа вы знаете?
    5. Как составить матрицу смежности?

    Домашняя работа: 1) д, е; 2. д, е, ж

    Объявление оценок.