Элементы теории графов

Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, или узлами, графа, линии - ребрами графа. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными. Две вершины, соединенные ребром, могут совпадать; такое ребро называется петлей. Число ребер, инцидентных вершине, называется степенью вершины. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом.
Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой; в этом случае оно называется направленным, или ориентированным, и изображается стрелкой. Граф, в котором все ребра ориентированные, называется ориентированным графом (орграфом); ребра орграфа часто называют дугами. Дуги именуются кратными, если они не только имеют общие вершины, но и совпадают по направлению. Иногда нужно рассматривать не весь граф, а его часть (часть вершин и часть ребер). Часть вершин и все инцидентные им ребра называются подграфом; все вершины и часть инцидентных им ребер называются суграфом. Циклом называется замкнутая цепь вершин.