Очевидно, что каждый неориентированный граф можно сделать ориентированным, заменив каждое ребро парой дуг идущих в противоположных направлениях (см. рисунок ниже). В связи с этим, можно рассматривать «смешанные» графы, которые могут содержать и ребра и дуги. Очевидно, что графы и орграфы являются частными случаями «смешанных» графов. В том параграфе под словом «граф» понимается «смешанный» граф, а под словом «ребро», понимается либо ребро, которое обозначаться будет [u, v], либо дуга, которая обозначаться будет (u, v).
Напомним, что граф состоит из пары множеств, для которых теоретико-множественные операции рассмотрены в главе Маршруты, пути, циклы.
Граф G1 = (V1, E1) называется подграфом графа G = (V, E), если V1⊆V и E1⊆E. Подграф G1 называется собственным подграфом графа G, если G1 не совпадает с G.
Определения. Пусть даны два графа G1 = (V1, E1) и G2 = (V2, E2).
1. Пересечением двух графов G1 и G2 называется граф G = (V, E), где V = V1∩V2, E = E1∩E2. Обозначение: G = G1∩G2.
2. Объединением двух графов G1 и G2 называется граф G = (V, E), где V = V1∪V2, E = E1∪E2. Обозначение: G = G1∪G2.
3. Симметрической разностью (или суммой по модулю 2) двух графов G1 и G2 называется граф G = (V, E), где V = V1∪V2, E = E1⊕E2 (E = E1∆E2). Обозначение: G = G1⊕G2.
4. Пусть задан граф G = (V, E) c |V| = n (т.е. с n вершинами) и без петель. На множестве вершин V построим полный граф Kn = (V, M). Дополнением графа без петель G(V, E) называется граф G’ = (V, M\E).
Пример. Пусть даны графы G1 = (V1, E1) и G2 = (V2, E2), где V1 = {a1, a2, a3}, E1 = {[a1, a2], (a2, a3)}, V2 = {a1, a2, a4}, E2 = {(a1, a2), (a4, a1)} (см. рисунок ниже).
1. Найдем G = G1∪G2 = (V, E), где V = {a1, a2, a3}∪{a1, a2, a4} = {a1, a2, a3, a4}, Е = {[a1, a2], (a2, a3)}∪{(a1, a2), (a4, a1)} = {[a1, a2], (a2, a3), (a4, a1)}.
2. Найдем G = G1∩G2 = (V, E), где V = {a1, a2, a3}∩{a1, a2, a4} = {a1, a2}, Е = {[a1, a2], (a2, a3)}∩{(a1, a2), (a4, a1)} = {(a1, a2)}.
3. Найдем G = G1⊕G2 = (V, E), где V = {a1, a2, a3}∪{a1, a2, a4} = {a1, a2, a3, a4}, Е = {[a1, a2], (a2, a3)}⊕{(a1, a2), (a4, a1)} = {(a2, a1), (a2, a3), (a4, a1)}.
Пример. Дополнением графа G, изображенного на рисунке ниже слева, является граф G’, изображенный на рисунке ниже справа.