20. Матрица смежности. Валентность вершины. Матрица инцидентности.

(матрица смежности, валентность вершины)

Опр: Пусть Г – граф с множеством вершин {V1,V2,…,Vn}. Матрицей смежности графа Г называется матрица n x m А=А(Г) элементы которой а_ij представляют собой число различных ребер соединяющих вершины Vi и Vj. Матрицы смежности (для не орграфа) с неизбежностью должны быть симметричными, т.к. количество ребер соединяющих вершины Vi и Vj = числу ребер соединяющих вершины Vj и Vi.

Если на главной диагонали имеется неулевой элемент, то там есть петля. При вычислении валентности нужно сложить элементы соответствующей строки(столбца). Ненулевой элемент на главной диагонали, при вычислении валентности умножается на 2.

Опр: Валентностью (степенью вершины) называется число ребер инцидентных вершине V. Если не оговаривается особо, то петля учитывается 2-жды при подсчете валентности. Граф у котор каждая вершина имеет одинаковую валентность R, называется правильным с валентностью R или R-валентным графом.

Опр: Если степень вершины (валентность графа)=0, то вершина называется изолированной, а если=1, то наз висячей.

Если в матрице строка или столбец состоят из нулей, то соответствующая вершина – изолированная. (матрица инцидентности)

а) не орграф с n вершинами и m ребрами В=[b_ij] i=1,…,n; j=1,…,m. b_ij=1, если вершина хi инцидентна ребру еi.

bij=0, если вершина xi неинцидентна ребру ei.

б) Орграф с n вершинами и m ребрами В=[bij]

bij=1, если ребро ej выходит из вершины xi,

bij=-1, если ребро ej входит в вершину xi, bij=0, если вершина xi неинцидентна ребру ej.

21. Виды графов

Графом (G,G(u,v),V E) называется совокупность множеств V и E между элементами которых определено отношение инцидентности, причем для каждого элемента еЕ найдется пара элементов из множества V, что e инцидентно этим элементам.

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

Способы задания графов.

1) геометрический.

2) табличный а) назовем вершину vi непосредственно предшествующей вершине vj, если существует дуга (vi,vj). Множество вершин, непосредственно предшествующих вершине vj, обозначим B(j), тогда граф можно задать в виде таблицы, где в первой троке записываются вершины, а во второй строке под ними вершины, непосредственно предшествующие соответствующей вершине.

Вершина vj называется непосредственно следующей за вершиной vi, если существует дуга (vi,vj). Множество вершин, непосредственно следующих за вершенной vi, обозначим как A(i). Таблица задается аналогично. Очевидно, ели граф не ориентирован, то множества А и В совпадают. б) таблица : в первой строке записываются ребра, а во второй строке – инцидентные им вершины. Причем если граф ориентирован, то на первом месте во второй строке ставится начальная, а на вором – конечная вершина. Если граф не ориентированный, то в любом порядке.

3) аналитический {V1,V2,V3,V4,(V2V3),(V4V2),(V4V3),(V3V2)}

4) матричный а) пусть имеем граф, содержащий n вершин и m ребер или дуг. Матрицей инцидентности называется матрица размера n x m(строки х столбцы), элемент которой Aij в случае не ориентированного графа равен 1, если вершина Vi инцидентна j-му ребру, и 0, в противном случае. Aij={1, Vi инц. j ребру; 0, если нет}. Если граф ориентированный, то Aij=-1, если вершина Vi начальная для j-й дуги, =1, если конечная, и 0, если вершина не инцидентна. Замечание: если мы имеем псевдограф(петлю), то в соответствующем месте Aij ставится любое число, отличное от 0 и +-1. б)матрица смежности. Матрицей смежности графа называется матрица n-го порядка(число вершин), элемент которой Aij=1, если есть дуга (vi,vj), и =0 в противном случае. Число единиц в матрице будет равно количеству дуг или удвоенному числу ребер.

Операции над графами.

Это справедливо и для псевдо- и для мультиграфов.

1. добавление ребра x=(Vi,Vj) в графе G. H=G+x, VH=VG, EH=EG{x}= EG{(Vi,Vj)}. Замечание: ребра добавляются только между несмежными вершинами, иначе получим мультиграф.

2. удаление ребра H=G-(Vi,Vj). VH=VG, EH=EG/{(Vi,Vj)}.

3. удаление вершины H=G-Vi, VH=VG/{Vi}, EH=EG/{x| x – ребра, инцидентные Vi)}.

4. объединение графов GH, VHVG, EHÈEG. Обычно полагают, что множества вершин и ребер не пересекаются. В противном случае операция объединения сводится к наложению графов друг на друга.

5. пересечение графов GH. Эта операция полагает, что пересечение вершин – не пустое множество. Тогда получаем граф, у которого пересекаются вершины и пересекаются ребра. VHVG, EHEG.

6. сложение графов G+H, VHVG, EHÈEGÈ{x=(u,v)|uVG, vVH}, т.е. из каждой вершины первого графа строим ребра к каждой вершине второго графа.