Автор работы: Пользователь скрыл имя, 16 Июня 2013 в 18:52, реферат
Дискретная математика – область математики, занимающаяся изучением свойств, структур конечного характера, которые возникают как внутри математики, так и в её приложениях. К числу таких конечных структур могут быть отнесены, например, конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, конечные автоматы, машина Тьюринга.
Дискретная (конечная) математика не связана с понятием предела, непрерывности и бесконечности. Дискретная математика имеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами.
ВВЕДЕНИЕ
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
МАТРИЦА СМЕЖНОСТИ
МАТРИЦА ИНЦИДЕНТНОСТИ
МАТРИЦА ИНЦИДЕНТНОСТИ ПРИМЕНЯЕТСЯ ПРИ АНАЛИЗЕ РЕШЕНИЙ
БИБЛИОГРАФИЯ
U1 U2 U3 U4 U5
V1 0 0 -1 -1 0
C = V2 -1 0 0 0 1
V3 1 -1 0 1 0
V4 0 1 1 0 -1
Для неориентированного графа в матрице инцидентности на пересечении строки с номером i и столбца с номером j стоит 1, если вершина Vi принадлежит ребру Uj и 0 - в противном случае.
теория граф матрица инцидентность
Например, для графа на рис.7 матрицей инцидентности является матрица D:
V
U3 V
U6
V
U5 V
U1 U2 U3 U4 U5 U6
Матрица инцидентности
применяется при анализе
Рассмотрим матрицы
1) Ориентированный граф:
U3
V1 V2 0 1 0 U1 U2 U3 U4
U1 U2 U4 E = 1 0 1 F = V1 1 -1 0 1
1 0 0 V2 -1 1 -1 0
V3
Матрица смежности
2) Неориентированный граф:
V3
U2 0 1 1 1 U1 U2 U3 U4 U5
U3 G = 1 0 1 0 V1 1 0 0 1 1
U5 1 1 0 1 N = V2 1 1 0 0 0
V2
U1
V1 U4 V4 V4 0 0 1 1 1
Матрица
инциндетности
Литература
1) В.Н. Бурков, Д.А. Новиков «Элементы теории графов»
2) А.В. Ганичева, В.П. Козлов. Аспект Пресс, 2005
3) А.Н. Кричивец, Е.В. Шикин, А.Г. Дьячков. 2005
Страница |
||