Прямым произведением 
графов 
и 
называется граф, у которого 
(т.е. вершины имеют вид 
где 
причём
(3)
соединены ребром в точности в следующих случаях: а) 
б) 
Например, если 
то графом будет являться треугольная призма (см. рис. 3.5).
Для графического построения графа следует нарисовать граф 
а затем каждую из вершин “раздуть” до графа 
Упражнение 3.5. Изобразить граф 
Решение (см. рис. 3.6).
Нарисуем граф 
с вершинами большого размера – для того, чтобы заменить каждую из них графом 
Соединение вершин осуществляется по правилу (3).
Граф 
(п - мерный куб). Его вершинами являются строчки 
где 
или 1. Две вершины 
и 
соединены ребром в том и только том случае, если строчки и имеют отличие ровно в одной позиции, т.е. существует такое 
что 
и 
при 
На рисунке 3.7 изображены графы 
и 
Для упрощения обозначений в записи вершин мы не пишем скобки и запятые, т.е. пишем 110 вместо 
Упражнение 3.6. Найти количество вершин и рёбер графа 
Решение. Так как вершины графа – это строчки и 
то всего вершин 
Далее, для вершины можно получить 
смежных с ней вершин, меняя поочерёдно каждую компоненту 
на противоположную 
Следовательно, из каждой вершины исходит ровно рёбер. Значит, общее количество рёбер равно 
(деление на 2 делается ввиду того, что иначе каждое ребро было бы подсчитано дважды). Итак, 
Подграф. Связный граф. Компоненты связности графа
Пусть – граф. Понятие подграфа имеет два различных не эквивалентных между собой определения.
Подграф в широком смысле графа 
– это граф 
где 
Подграф в узком смысле – это граф 
где 
и 
Иными словами, для построения у графа подграфа в широком смысле надо выделить какое-либо множество вершин и некоторые из них соединить рёбрами, взятыми из графа 
Для получения подграфа в узком смысле надо взять какое-либо множество вершин и соединить их в точности теми рёбрами, которыми они соединялись в графе На рисунке 8 изображены графы и такие, что – подграф графа в широком, но не в узком смысле. Чтобы получить из него подграф в узком смысле, следует добавить ребро 
Далее словом “подграф” мы будем называть подграф в широком смысле.
Граф называется связным, если для любых двух его вершин 
и 
существует путь из в 
Будем считать, что из в всегда существует путь нулевой длины (если длину определять по количеству рёбер). Любой граф является объединением своих связных подграфов 
таких, что не существует рёбер (а значит, и путей), соединяющих вершины из разных 
Эти подграфы называются компонентами связности графа
Например, граф изображённый на рисунке 3.9, состоит из трёх компонент связности.
У связного графа 
