АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Прочитайте:
  1. Aлгоритмы на графах
  2. b) и с) Происхождение эксогамии и ее отношение к тотемизму
  3. B) любые сведения, полученные в ходе производства по делу с соблюдением требований уголовно-процессуального законодательства, имеющие отношение к делу
  4. III модуль. Соотношение факторов генотипа и среды в возникновении наследственных болезней и проблем психического дизонтогенеза
  5. V. Одной из причин кардиалгии являются психогенные состояния.
  6. А знаете ли Вы, что такое ПНЖК?
  7. А – отношение женщины к себе беременной
  8. Активаторы церебрального метаболизма
  9. Б — соотношение лицевого черепа взрослого и новорожденного
  10. Б) отношение численности занятого населения к численности трудовых ресурсов.

Пусть задан (n,m) – орграф G = (Х,А). Матрица инцидентности графа G обозначается через В = [bij] и является матрицей размерности n ´ m, определяемой следующим образом:

bij = 1, если xi является начальной вершиной дуги аj,

bij = -1, если xi является конечной вершиной дуги аj,

bij = 0, если xi не является концевой вершиной дуги аj, или если аj - петля.

Пример 5. Для графа G матрица инцидентности имеет вид

  a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
x1 1 1 0 0 0 0 0 -1 -1 0
x2 -1 0 -1 1 0 0 0 0 0 0
x3 0 -1 1 0 -1 0 0 0 0 1
x4 0 0 0 0 1 -1 0 0 0 0
x5 0 0 0 -1 0 1 -1 1 0 0
x6 0 0 0 0 0 0 1 0 1 -1

 

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

- либо 1 и –1, а остальные нули;

- либо все нули.

Если G – неориентированный граф, то его матрица инциденций определяется также, за исключением того, что все элементы, равные -1, заменяются на +1.

Очевидно, что матрица инциденций нечувствительна к петлям.

§ 2.4. Подграфы

Для заданного графа можно определить подграфы. Рассмотрим два вида подграфов: остовные и порождённые.

Остовной подграф. Пусть дан неориентированный граф G=(V,E). Остовным подграфом GP графа G называется граф (V,EP), для которого ЕР Ì Е. Таким образом, остовной подграф имеет то же множество вершин, что и исходный граф G, но не все его рёбра.

Порождённый подграф. Пусть дан орграф G=(Х,А). Порождённым подграфом GS графа G называется граф (XS,AS), для которого XS Ì X и AS Ì A, причём в АS входят только те дуги, обе концевые вершины которых принадлежат множеству XS; для каждой вершины xi Î XS выполняется условие

ГS(xi) = Г(xi)Ç XS.

Таким образом, порождённый подграф состоит из подмножества вершин XS множества Х вершин исходного графа и всех таких дуг графа G, у которых начальные и конечные вершины принадлежат подмножеству XS. Иногда порождённый подграф GS обозначают <XS>. При построении порождённого графа из исходного удаляются некоторые вершины и все инцидентные удалённым вершинам дуги (рёбра).

Дата добавления: 2015-09-27 | Просмотры: 693 | Нарушение авторских прав

При использовании материала ссылка на сайт medlec.org обязательна! (0.005 сек.)