1. Граф (G) состоит из конечного непустого множества V, содержащего P вершин и заданного множества E, содержащего q неупорядоченных пар различных вершин из V.
Каждую пару х={u,v} вершин в Е называют ребром графа G и говорят, что х соединяет вершины u и v. Если х соединяет u и v, то u и v - смежные вершины. Иногда обозначается х = u,v.
2. Вершина u и ребро х инцидентны, также как вершина v и ребро x инцидентны. Если два ребра x и y инцидентны одной вершине, то они называются смежными.
3. Граф с Р вершинами и q ребрами называется (p,q)-графом. Граф (1,0) - называется тривиальным.
На рис. u и v - вершины, причем смежные, т.к.
они инцидентны одному ребру (соединяются одним ребром). Ребра x и y - смежные, т.к. они инцидентны одной и той же вершине. x и z - несмежные ребра, хотя и пересекаются в одной точке, но у них нет общей вершины (не инцидентны одной вершине).
