До графів визначають дві специфічні операції: 1)вилучення ребра. Результатом цієї операції буде G-е = {V,E-{e}}. 2)вилучення вершини: G-v = {V-{v},EÇ(V-{v})(2)} 3)доповнення до графа. Доповненням графа G називається G, який визначається наступним чином: G=(V,(V(2)-E)). Доповненням до графа G буде G. Для довільного графа об’єднання G та G буде повний граф. Якщо в графі G з n – вершинами, степінь вершини дорівнює k, то в графі G доповненням степінь цієї вершини буде n-k-1.
Маршрути, ланцюги, цикли.
Маршрут називається ланцюгом, якщо всі його ребра попарно різні. Цикл – це замкнений ланцюг (послідовність ребер або дуг). В графі з n – вершинами степінь вершини можна позначити від 0 до n-1. Маршрутом в графі G називається послідовність вершин та ребер:(V0,e1,V1e2,…,en,Vn). Ребра з індексом у еі+1 називаються сусідніми і мають одну спільну вершину. Число n називається довжиною маршрутом. Маршрут називається тривіальним, який складається тільки з однієї вершини та множини n.
Ознаки зв’язності
Неограф назив. зв’язним, якщо будь-які його 2 неспівпадаючі вершини пов’язані маршрутом. Граф назив. сильнозв’язним, якщо для кожної пари різних вершин А та В є маршрут з А в В і з В в А. Будь-який максимальний за включенням сильно зв’язаний підграф даного графа назив. його компонентою зв’язності.
