CAJ | 학술논문

按照同构图的定义判断两个图是否同构，最坏情况下其时间复杂度是O(N！)，当结点数N比较大时，计算速度非常慢，针对该问题，提出一种通过统计结点间距离和按照距离分层，计算同层结点间的关联边数以及关联结点数来研究图中各结点差异的算法，该算法可以给出两个图的结点间可能的对应关系。如果两个图的结点距离数组及对应结点的层结点关联数组不能一一对应，其时间复杂度仅为O(N4)，否则，根据结点间可能的对应关系，避免遍历所有结点序号的交换，计算量可以成倍地下降。
안조동구도적정의판단량개도시부동구，최배정황하기시간복잡도시O(N！)，당결점수N비교대시，계산속도비상만，침대해문제，제출일충통과통계결점간거리화안조거리분층，계산동층결점간적관련변수이급관련결점수래연구도중각결점차이적산법，해산법가이급출량개도적결점간가능적대응관계。여과량개도적결점거리수조급대응결점적층결점관련수조불능일일대응，기시간복잡도부위O(N4)，부칙，근거결점간가능적대응관계，피면편력소유결점서호적교환，계산량가이성배지하강。
To determine two graphs are isomorphic or not by the definition of graph isomorphism, at worst, the time complexity is O(N!). Against this problem, it introduces an algorithm which is based on the distance statistics of the vertices. Vertices are stratified by distance, by counting the numbers of related edges and related vertices of vertices which are isometric. The algorithm shows the difference of the vertices, and points out the vertices correspondence of two graphs. If the vertices distance array and layer related vertices array of two graphs are not one-to-one, the time complexity of the algorithm is only O(N4). If they are one-to-one, swap the sequence of the vertices in one graph which may correspond to the vertex in the other graph, avoid swapping the sequence of all vertices, in this condition, the time complexity is reduced by many times.