Графы, мультиграфы, псевдографы, орграфы. Изоморфизм графов

Определение: (p,q) – граф, есть система объектов. G=(V,E), где V={v1, v2,…,vp} – множество вершин, E={ e1=(vi1,vj1), e2=(vi2,vj2),…, eq=(viq,vjq)}ik ≠ jk k=1,2,3,..,q – множество неориентированных ребер ik≠j1, k=1..q.

Две вершины графа G смежные (соседние), если они соединены в G ребром. Если граф G имеет ребро e=(u,v), то вершина u и ребро e (равно как и вершина v и ребро e) инцидентны (принадлежат друг другу). Изолированная вершина не инцидентна ни одному ребру. Висячая (концевая) вершина (лист) инцидентна только одному ребру. Два ребра, инцидентные одной вершине, называются смежными.

Граф G1=(V1,E1) равен графу G2=(V2,E2) ⇔ V1=V2, E1=E2. Графы G1 и G2 изоморфны, если существует взаимнооднозначное соответствие φ: V1→V2, сохраняющее отношение смежности (соседства) вершин, т.е. если (u,v)∈E1 ↔ ((&phi(u),&phi(v))&isinE2).

Граф G1=(V1,E1) есть подграф графа G2=(V2,E2) ⇔ V1 ⊆ V2 E1 ⊆ E2. Если V1=V2, то подграф G1 называется остовным подграфом графа G2.

Подграф G1 графа G называется порожденным множеством вершин V1, (натянутым на множество вершин V1), если V1⊆V, и ∀u,v∈V1 (e=(u,v)∈E → e∈Е1).

Граф Кр называется полным, если каждые его 2 вершины связаны ребром. Петля, есть ребро e=(u,u). Кратные (параллельные) ребра соединяют одну и туже пару вершин.

Мультиграф допускает кратные ребра, но не допускает петель.

Песевдограф допускает и кратные ребра, и петли.

Замечание: Граф не допускает кратных ребер и петель.

Определение: Орграф (ориентированный, направленный граф) – есть граф, где все ребра ориентированны.

Замечание: также можно говорить об ориентированных мульти и псевдографах.


Оставить комментарий





Статистика

Рейтинг@Mail.ru