Определение: (p,q) – граф, есть система объектов. G=(V,E), где V={v₁, v₂,…,v_p} – множество вершин, E={ e₁=(v_i1,v_j1), e₂=(v_i2,v_j2),…, e_q=(v_iq,v_jq)}i_k ≠ j_k k=1,2,3,..,q – множество неориентированных ребер i_k≠j₁, k=1..q.

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

Граф G₁=(V₁,E₁) равен графу G₂=(V₂,E₂) ⇔ V₁=V₂, E₁=E₂. Графы G₁ и G₂ изоморфны, если существует взаимнооднозначное соответствие φ: V₁→V₂, сохраняющее отношение смежности (соседства) вершин, т.е. если (u,v)∈E₁ ↔ ((&phi(u),&phi(v))&isinE₂).

Граф G₁=(V₁,E₁) есть подграф графа G₂=(V₂,E₂) ⇔ V₁ ⊆ V₂ E₁ ⊆ E₂. Если V₁=V₂, то подграф G₁ называется остовным подграфом графа G₂.

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

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

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

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

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

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

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

Комментарии запрещены.