Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ




Читайте также:
  1. AGIL. Системный подход в теории Т. Парсонса.
  2. C. Элементы
  3. V Теории личности в зарубежной психологии.
  4. V. СОВРЕМЕННЫЕ ПСИХОЛОГИЧЕСКИЕ ТЕОРИИ ЛИЧНОСТИ
  5. Админ теории менед-та(А Файоль) и теория бюрократического построения орг-и(М Вебер)
  6. Аксиоматический способ построения теории
  7. Артиллерийский выстрел и его элементы. Классификация артиллерийских выстрелов.
  8. Ауман Р., Шеллинг Т. о теории игр.
  9. Б11-в2 Основные элементы книги
  10. Базовые понятия теории общественного выбора.

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

Определение. Граф Г=(V, R) – фигура из множества точек вершин графа и множества отрезков, или дуг ребер графа, соединяющих его некоторые вершины.

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

 

 

 

Подграф Г’=(V’, R’) графа Г – это некоторая часть графа Г: V’ V, R’ R.

Как хранить граф в компьютере?

Определение. Матрица смежности :

 

Очевидно, что А – симметричная матрица, то есть .

 

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

 


Дата добавления: 2015-07-26; просмотров: 3; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты