Тема работы:

Теория графов (МЕТОДИЧЕСКИЕ УКАЗАНИЯ по подготовке к контрольным работам по дисциплине «Дискретная математика»)

• Номер работы:
  414232
• Раздел:
  Все что не попадает в другие рубрики   →   Математика (ВСЕ направления)
• Год сдачи:
  11.03.2011
• Стоимость:
  500 руб.
• Количество страниц:
  35 стр.
• Содержание:
  Краткий перечень основных понятий теории графов ……………….. 4
  Понятия смежности, инцидентности, степени ……………………….. 7
  Маршруты и пути ………………………………………………………. 7
  Матрицы смежности и инцидентности…..……………………………. 7
  Связность. Компоненты связности …………………………………….. 8
  Матрицы достижимости и связности ………….………………………. 9
  Расстояния в графе …………………………..…………….……………. 9
  Образ и прообраз вершины и множества вершин …………..……….. 10
  Нагруженные графы ………………..………………………………….. 11
  Деревья и циклы …………………………………….………….……… 12
  
  Решение контрольных задач по теме «Теория графов»……………………………………………...…………………... 13
  Задание 1. Компоненты сильной связности ориентированного графа.……………………………………………………………………. 13
  Задание 2. Расстояния в ориентированном графе ..………………...... 16
  Задание 3. Минимальный путь в нагруженном ориентированном графе ...……...…………………………………………………………... 20
  Задание 4. Эйлеровы циклы и цепи ……..………………………….… 23
  Задание 5. Минимальное основное дерево...………...…………...…… 25
  Задание 6. Задача о коммивояжёре...………...…………...…………… 27
  
  Задания для самостоятельного решения ………….………......……… 34
  
  Список литературы…………………………………………………..…. 37
  
• Выдержка из работы:
  Основная часть:
  Последовательность v1x1v2x2v3...xkvk+1, (где k1, viV, i=1,...,k+1, xiX, j=1,...,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj,vj+1} (для ориентированного графа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).
  
  Пример
  В графе, изображенном на рис.4, v1x1v2x2v3x4v4x3v2 - маршрут, v2x2v3x4v4 – подмаршрут;
  маршрут можно восстановить и по такой записи x1x2x4x3 ;
  если кратности ребер (дуг) равны 1, можно записать и так v1v2v3v4v2 .
  
  Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.
  Цикл − замкнутая цепь (в неориентированном графе).
  Контур − замкнутый путь (в ориентированном графе).
  Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.
  Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.
  Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.
  Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.
  Длина маршрута (пути) − число ребер в маршруте (дуг в пути).
  Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.
  Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.
  
  Матрицы смежности и инцидентности
  Пусть D=(V,X) ориентированный граф, V={v1,...,vn}, X={x1,...,xm}.
  Матрица смежности ориентированного графа D − квадратная матрица
  A(D)=[aij] порядка n, где
  
  Матрица инцидентности − матрица B(D)=[bij] порядка nm, где
  
  Матрицей смежности неориентированного графа G=(V,X) называется квадратная симметричная матрица A(G)=[aij] порядка n, где
  .
  Матрица инцидентности графа G называется матрица B(G)=[bij] порядка nm, где
  
  
  Связность. Компоненты связности
  Подграфом графа G (ориентированного графа D) называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G (D).
  Подграф называется собственным, если он отличен от самого графа.
  Говорят, что вершина w ориентированного графа D (графа G) достижима из вершины v, если либо w=v, либо существует путь (маршрут) из v в w.
  Граф (ориентированный граф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.
  Компонентой связности графа G (сильной связности ориентированного графа D) называется его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (ориентированного графа D).
  
  Матрицы достижимости и связности
  Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v1,…, vn}. Обозначим через Ak=[a(k)ij] k-ю степень матрицы смежности A(D).
  Элемент a(k)ij матрицы Ak ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из vi в vj.
  Матрица достижимости ориентированного графа D − квадратная матрица T(D)=[tij] порядка n, элементы которой равны
  
  Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[sij] порядка n, элементы которой равны
  ...........