Дискретная математика 3 (стр. 6 из 10)
E={{v1, v2}, {v1, v3}, {v2, v3}, {v3, v4}, {v5, v6}}.
v1, v3, v4 – простая цепь,
v1, v3, v2, v1, v3, v4 – цепь (не простая),
v3, v1, v2, v4 – не цепь.
v1, v3, v2, v1 – цикл,
v4, v3, v1, v2, v3, v4 – цепь с совпадающими концами, но не цикл, так как цепь не простая.
dg v1=dg v2=2, dg v3=3, dg v4=dg v5=1, dg v7=0.
#6. V={v1, v2, v3, v4, v5, v6},E={(v1, v2), (v1, v3), (v2, v1), (v2, v3), (v2, v4), (v3, v1), (v3, v4), (v5, v6), (v6, v4)}.
v1, v2, v3, v4 – простой путь,
v1, v2, v3, v1, v3, v4 – путь (не простой),
v3, v1, v2, v3 – контур,
v3, v1, v2, v1, v3 – замкнутый путь, но не контур,
v1, v3, v4, v6 – не путь.
dg-(v1)=dg-(v3)=2, dg+(v1)=dg+(v3)=2, dg(v1)=dg(v3)=4;
dg-(v2)=1, dg+(v2)=3, dg(v2)=4;
dg-(v4)=3, dg+(v4)=0, dg(v4)=3;
dg-(v5)=0, dg+(v5)=1, dg(v5)=1;
dg-(v6)=1, dg+(v6)=1, dg(v6)=2.
Определение 5. Вершина степени 0 называется изолированной, вершина степени 1 называется висячей (или концевой).
В #5 вершина v7 – изолированная; а вершины v4, v5, v6 – висячие.
Легко видеть, что если сложить степени всех вершин графа, то получится четное число равное удвоенному числу ребер. Этот результат, известный еще 200 лет назад Эйлеру часто называют леммой о рукопожатиях.
§3. Изоморфизм графов. Подграф. Связные графы.
Определение 6. Два графа G1 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер соединяющих любые две вершины в G1 равно числу ребер, соединяющих соответствующие вершины в G2.
#7.v1«u1, v2«u3, v3«u5, v4«u2, v5«u4, v6«u6.
v1«w1, v2«w3, v3«w6,
v4«w5, v5«w4, v6«w2.
Определение 7.Подграфом графа G называется граф G1=(V(G1), E(G1)), все вершины которого принадлежат V(G), а все ребра принадлежат E(G), то есть V(G1)ÍV(G), E(G1)ÍE(G).
Замечание. Так как в определении 7 пара G1=(V(G1), E(G1)) является графом, то для любого ребра {u, v}ÎE(G1) или дуги (u, v)ÎE(G1) предполагается, конечно, что u, vÎV(G1).
Если V(G1)ÌV(G) или E(G1)ÌE(G), то G1 называют собственным подграфом графа G, если V(G1)=V(G), то G1 называют остовным подграфом графа G.
Определение 8. Подграф G1 неориентированного (ориентированного) графа G называют подграфом, порожденным множеством вершин V(G1)ÍV(G), если каждое ребро (дуга)( тогда и только тогда принадлежит E(G1)ÍE(G), когда его (ее) концы принадлежат V(G1).
Отметим, что подграф графа G порожденный множеством вершин V(G1), в отличие от произвольного подграфа графа G с множеством вершин V(G1) должен включать все ребра (дуги), концы которых принадлежат множеству V(G1).#8. Граф G:
V(G)={u, v, w, z, x},
E(G)={{u, v}, {u, v}, {v, w}, {v, w}, {w, w}, {w, z}, {z, z}, {w, x}, {z, x}}.
Собственный подграф G1 не является порожденным подграфом:
V(G1)={u, v, w}ÌV(G),
E(G1)={{u, v}, {v, w}, {w, w}}.
G2 – подграф, порожденный множеством
вершин u, v, w:
V(G2)={u, v, w}.
E(G2)={{u, v}, {u, v}, {v, w}, {v, w}, {w, w}}.
Определение 9. Подграф G1ÍG называют максимальным подграфом, если он не является собственным подграфом никакого другого подграфа графа G.
#9. G1 G2 G3 G4 G5
Подграфы G1, G2, G3, G4 являются максимальными ациклическими подграфами графа G5. Они также являются собственными и основными подграфами.
Следующее важное понятие снова введем параллельно для неориентированных и ориентированных графов.
| Неориентированные графы | Ориентированные графы |
| Неориентированный граф называют связным, если любые две его вершины u и v соединены цепью. | Ориентированный граф называется связным, если для любых двух его вершин u и v вершина v достижима из вершины u или вершина u достижима из вершины v. |
Определение 10.Компонента связности (или просто компонента) неориентированного (ориентированного) графа – это его максимальный связный подграф.
В неориентированном графе две вершины, соединенные цепью, связаны отношением достижимости, которое является отношением эквивалентности:
1. Рефлексивность. Вершина u достижима сама с собой, так как существует цепь u.
2. Симметричность. Если вершина v достижима из u, то существует цепь u0=u, u1, …, un=v, но так как граф неориентированный, то отсюда следует, что существует цепь v=un, un-1, …, u1, u0=u, то есть вершина u достижима из вершины v.
3. Транзитивность. Пусть v достижима из u и w достижима из v. следовательно, существует цепь u=u0, u1, u2, …, un=v и существует цепь v=v0, v1, v2, …, vm=w. Но тогда существует цепь u0=u, u1, …, un=v=v0, v1, v2, …, vm=w, то есть w достижима из u.