广西科学院学报
廣西科學院學報
엄서과학원학보
JOURNAL OF GUANGXI ACADEMY OF SCIENCES
2006年
1期
1-5
,共5页
哈密顿图%欧拉图%点回路%边回路%回路
哈密頓圖%歐拉圖%點迴路%邊迴路%迴路
합밀돈도%구랍도%점회로%변회로%회로
分析由延长而形成哈密顿回路、欧拉回路的特点,得出求图G(n,m)的最大回路算法:给定始结点xi和始边ei(xj).采用最长路回延长法,对点xi和边ei(xj)分别求最长路回HE序列,在对点xi求最长路回HE序列中,当出现长度为n的点回路的最长项,边ei(xj)出现长度为m的边回路的最长项,或延长后所得路径中没有元素,便结束延长;如对点xi有长度为n的最大点回路最长项,则G(n,m)为哈密顿图;如对边ei(xj)有长度为m的最大边回路最长项,则G(n,m)为欧拉图.
分析由延長而形成哈密頓迴路、歐拉迴路的特點,得齣求圖G(n,m)的最大迴路算法:給定始結點xi和始邊ei(xj).採用最長路迴延長法,對點xi和邊ei(xj)分彆求最長路迴HE序列,在對點xi求最長路迴HE序列中,噹齣現長度為n的點迴路的最長項,邊ei(xj)齣現長度為m的邊迴路的最長項,或延長後所得路徑中沒有元素,便結束延長;如對點xi有長度為n的最大點迴路最長項,則G(n,m)為哈密頓圖;如對邊ei(xj)有長度為m的最大邊迴路最長項,則G(n,m)為歐拉圖.
분석유연장이형성합밀돈회로、구랍회로적특점,득출구도G(n,m)적최대회로산법:급정시결점xi화시변ei(xj).채용최장로회연장법,대점xi화변ei(xj)분별구최장로회HE서렬,재대점xi구최장로회HE서렬중,당출현장도위n적점회로적최장항,변ei(xj)출현장도위m적변회로적최장항,혹연장후소득로경중몰유원소,편결속연장;여대점xi유장도위n적최대점회로최장항,칙G(n,m)위합밀돈도;여대변ei(xj)유장도위m적최대변회로최장항,칙G(n,m)위구랍도.
