Дискретная математика

121 называются инцидентными ребру х, ребро х считается инцидентным вершинам >',•и у,. Если два различных ребра хну инцидентны одной и той же вершине, то они называются смежными. Граф с п вершинами и т ребрами называется (и.и^-графом. На рис. 5.2, б) приведены (3,0), (3,1), (3,2) и (3,3) графы. (1,0) граф называется тривиалънъш. Рассмотрим (4,3) граф, изобралсенньш на рис. 5.3, а). В этом 1'рафе вершина v/ инцидентна ребру jc/, а рёбра л-/ их2 смежные ребра. Граф, в котором вершины могут соединяться более чем одним ребром, называется мультиграфом. v; X, / Хз (Г^ V2 ^2 а) б) в) Рис.5.3 Из определения следует, что в графе не может быть ребер, начинающихся и оканчивающихся в одной вершине, - так иaзывae^iыx петель. Граф, в котором есть дополнительные кратные ребра и петли, называется псевдографом. Орграфом или ориентированным графом называется совокупность, состоящая из конечного множества V точек, называемых вершинами, и множества упорядоченных пар различных вершин из V, называемых дугами. Множество дуг орфафа обозначим тоже через X, а дуги как упорядоченную пару (vi,vj) или Xij (i,j=\,2,...,n). В орграфе две вершины v и и могут быть соединены одной или двумя дугами. Дуги {v,v) и (u.v) считаются симметричньши дугами. На рис. 5.3, б) приведён орграф с симметричными дугами. Направленным орграфо.ы считается орграф, не имеющий симметричных дуг. На Рис. 5.3, в) приведён направленный орграф. Граф, в котором имеются и дуги, и рёбра, называется смешанным графом. Граф G=(KX), состоящий только из вершин, называется нуль - графо.м. Граф G=(V,X), в котором любые две вершины соединены ребром, называется полным.. Полный граф с п вершинами обозначают через К„. На рис 5.4: а) - нуль - граф,, б) - ориентированный граф (орграф); в) - смешанный граф, г) - полный (неориентированный) граф - граф /<",?.