Основные понятия и определения теории графов

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

X = {x₀, x₁, x₂, x₃, x_4, x₅}.

а)

б)

в)

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