Графов изоморфизм

- отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой наз. взаимно однозначное отображение вершин и ребер одного графа соответственно на вершиныи ребра другого графа, при к-ром сохраняется отношение инцидентности. Два графа наз. изоморфными, если существует изоморфное отображение одного из этих графов на другой. Графы G1 и G2, представленные на рис., не изоморфны, a G1 и G3 изоморфны. Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и данным числом ребер конечно. Подобным образом можно определить изоморфизм ориентированных графов, гиперграфов и сетей. [img: http://localhost:8080/file/010429-124.jpg] [img: http://localhost:8080/file/010429-125.jpg] [img: http://localhost:8080/file/010429-127.jpg] Проблема установления Г. и. является важной проблемой теории графов. Для нек-рых классов графов имеются алгоритмы, позволяющие установить изоморфизм достаточно эффективно (напр., для деревьев или плоских графов, см. [1]). Для нек-рых классов графов с пвершинами доказана однозначная (с точностью до изоморфизма) восстанавливаемость графа по набору всех его [img: http://localhost:8080/file/010429-126.jpg] -вершин ных подграфов [img: http://localhost:8080/file/010429-128.jpg], получаемых удалением всевозможных вершин [img: http://localhost:8080/file/010429-129.jpg]. Это установлено, в частности, для деревьев и турниров (при [img: http://localhost:8080/file/010429-130.jpg]).