Презентация на тему "Основные понятия теории графов"

Содержание

• 
  Слайд 1
  

  МИНОБРНАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИФедеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет»Экономический факультетКафедра экономической кибернетики

  Основные понятия теории графов Выполнил студент группы 2.1: Колычев Алексей Сергеевич Научный руководитель: доцент, кандидат экономических наук Рунова Лидия Павловна

• 
  Слайд 2

  Оглавление

  1. Базовое определение графа и его составляющих 2.Пути, маршруты, цепи и циклы 3.Подграфы 4.Список литературы

• 
  Слайд 3

  Базовое определение графа и его составляющих

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

• 
  Слайд 4
  

  Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

• 
  Слайд 5

  Пути, маршруты, цепи и циклы

  Путь — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Маршрут – это путь, ориентацией дуг которого можно пренебречь. Цепь – это маршрут, в котором все ребра попарно различны.Цикл - это замкнутый маршрут, являющийся цепью. Пример циклического графа

• 
  Слайд 6

  Граф и отношения делимости

  Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на 2.

• 
  Слайд 7

  Подграфы

  Подграф графа - это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра. Подграф, порожденный множеством вершин U – это подграф, множество вершин которого - U содержащий те и только те ребра, оба конца которых входят в U. Граф называется связным, если любая пара его вершин связана. Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

• 
  Слайд 8

  Деревья

  Дерево — это связный граф без циклов.Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья. Лес – это граф без цикла. Вершины степени 1 в дереве называются листьями. 

• 
  Слайд 9

  В теории графов применяются:

  Матрица инцинденций - это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующих рёбрам. Матрица смежности - это матрица n×n где n - число вершин, где bij = 1, если существует ребро, идещее из вершины х в вершину у и bij = 0 в противном случае.

• 
  Слайд 10

  Список использованной литературы:

  http://matmetod-popova.narod.ru/theme213.htm http://www.algolib.narod.ru/Graph/Base.html http://lib.vvsu.ru/books/Bakalavr01/page0221.asp http://dmtsoft.ru/bn/391/as/oneaticleshablon/

• 
  Слайд 11

  СПАСИБО ЗА ВНИМАНИЕ!