Пусть дано множество Х, которое состоит из элементов, называемых точками. Дан закон, позволяющий установить соотношение Т между каждым элементом множества Х и некоторыми из его подмножеств. Обозначим через Тх некое подмножество множества Х, отвечающее элементу х множества Х. Две математические величины – «множество Х» и «соответствие Т» - определяют граф G, обозначаемый как G = (X, T). Элементы множества Х будем изображать точками, и называть вершинами графа. Соотношения Т будем изображать отрезками (иногда ориентированными), соединяющими элемент с элементами подмножества Тх, и называть ребрами или дугами графа. Граф G называется конечным, если число его вершин конечно. На рис.1,а показан граф, определяемый множеством

X = {x0, x1, x2, x3, x4, x5}.

а)

б)

в)

Рис.1. Различные графы: а – граф, определяемый множеством вершин Х = {x0, x1, …, x5}; б – нуль граф; в – граф, определяемый множеством вершин Х = {a, b, c, d}.