Степень - вершина - граф
Cтраница 2
 |
Графики зависимости условной ЦФ от числа итераций.| График зависимости времени решения от числа итераций. [16] |
Задача распознавания изоморфизма графов является одной из важнейших комбинаторно-логических задач. Проблема определения изоморфизма двух графов, расположенных на плоскости, заключается в получении одного графа из другого путем перенумерации их вершин. Другими словами, необходимо найти подстановку множество вершин, переводящую один граф в другой. Как отмечалось выше, наибольшую трудность при определении изоморфизма представляют однородные графы. Было случайно сгенерировано сто однородных графов, а затем в этих же графах выполнена случайная перестановка их вершин. Следовательно, заранее было известно, что анализируются изоморфные графы, в которых нужно определить подстановку, переводящую один граф в другой. В таблице 7.6 в столбце 2 приведено количество вершин исследуемых графов. В столбце 3 указаны локальные степени вершин графов. [17]
Страницы: 1 2