Графы с цветными ребрами
    Если на плоскости расположены несколько точек и линии, каждая из которых соединяет пару из наших точек, то говорят, что задан граф. Точки называются вершинами графа, а линии - его ребрами. Ребра графа могут быть окрашены в несколько цветов, тогда его называют графом с цветными ребрами. На рисунке изображен граф с пятью вершинами и ребрами двух цветов






    Этот же граф можно изобразить и другими непохожими рисунками







   Действительно, граф с цветными ребрами можно задавать таблицей с n строками и n столбцами, где n-число вершин. Для этого нужно занумеровать вершины, и на пересечении i-й строки и j-ro столбца таблицы написать цвет ребра, соединяющего i-ю и j-ю вершины. Легко сообразить, что можно занумеровать вершины графов на рисунках так, что таблицы окажутся одинаковыми. Именно поэтому мы и говорим, что это - один и тот же граф.
Здесь рассматриваются только такие графы, у которых каждая пара вершин соединена ребром. Такие графы называют полными. Однако, поскольку других графов здесь не рассматривается, мы не будем каждый раз писать слово "полный". Применение графов с цветными ребрами упрощает решение некоторых задач и делает их более наглядными.

Закрыть