Автор: Пользователь скрыл имя, 14 Января 2012 в 13:54, доклад
Под множеством S будем понимать любое собрвние определенных и различных между собой объектов мыслимое как единое целое. Эти объекты называются элементами множества S. Для любого объекта можно установить принадлежит он множеству или нет. A={1,2,3..}, A={x|p(x)} — обозначения.
∑[vЄV] δ(с.+)(v)=∑[vЄV] δ(с.-)(v)=m(D).
ИЗОМОРФИЗМ. ГОМЕОМОРФИЗМ.
G1(V1,X1), G2(V2,X2) называются
изоморфными, если существует
биективное (взаимооднозначное)
отображение φ:V1àV2, сохраняющее смежность, т.е. если {v,w}ЄX1 <=> {φ(v),φ(w)}ЄX2. Орграфы D1(V1,X1), D2=(V2,X2) называются изоморфными, если существует отображение φ:V1àV2, (v,w)ЄX1 <=> (φ(v),φ(w))ЄX2. Свойства изоморфных графов: - если G1,G2 — изоморфны и φ:V1àV2 — для любого vЄV1, δ(v)=δ(φ(v)), - m(G1)=m(G2), n(G1)=n(G2). Для орграфа свойства аналогичны, для любого vЄV1, δ(с.-)(v)=δ(инд.-)(φ(v))
, δ(с.+)(v)=δ(с.+)(φ(v)), m(D1)=m(D2), n(D1)=n(D2). Примеры изоморфных графов см. на рисунке. УТВЕРЖДЕНИЕ: изоморфизм групп
является отношением эквивалентности на множестве
графов или орграфов. ОПРЕДЕЛЕНИЕ: операцией по
разбиению дуги (u,v) в орграфе D(v,x) называется
операция, которая состоит из удаления добавления к V
вешины w. Орграф D2 называется разбиением орграфа D1
, если D2 получается из D1 путем последовательного
применения интеграции дуг. Орграфы D1,D2(G1,G2) называются гомеоморфными, если существует их подразделение, которое является изоморным. Если степени всех вершин равны k, то граф называется регулярным в степени k. Граф исходящий из 1 вершины называется тривиальным. Двудольным называется граф G(V,X),
такой, что он разбит V1,V2(v1Uv2=v, v1∩v2≈Ø),
каждое ребро инцедентно вершине из v1 и v2.