與無(wú)向圖及有向圖中距離有關(guān)的三個(gè)問(wèn)題.pdf

1、本文主要研究了與無(wú)向圖及有向圖中距離有關(guān)的三個(gè)問(wèn)題：(1)Km∨Kn(m≥1，n≥1)的最小直徑定向，(2)有向圖中不相交的擬核，(3)離心有向圖. 對(duì)于圖G，設(shè)D為G的具有最小直徑的定向圖，定義f(G)=diamD.本文我們主要探索圖Km∨Kn(m≥1，n≥1)的最小直徑定向.一些特殊情況是已知的：當(dāng)m=1且n≥1；m=2或m≥4且n=1；m=3且n=1時(shí)，f(Km∨Kn)分別為∞，2，3. 因此，我們只考慮當(dāng)m≥2且

2、n≥2的情況，得到如下結(jié)果：(1)當(dāng)m=2，3，n≥2和m=n=4時(shí)，f(Km∨Kn)=3；(2)當(dāng)m≥5且m是奇數(shù)，2≤n≤(m「m-2」)-m時(shí)，f(Km∨Kn)=2；(3)當(dāng)m≥5且m是奇數(shù)，n≥(m「m-2」)-「m-2」+1時(shí)，f(Km∨Kn)=3；(4)當(dāng)m≥4且m被4整除，2≤n≤(mm-2)-(m-2+1)時(shí)，f(Km∨Kn)=2；(5)當(dāng)m≥6且m被4除余2，2≤n≤(mm-2)-m-2時(shí)，f(Km∨Kn)=2；(6)

3、當(dāng)m≥4且m是偶數(shù)，n≥(mm-2)-m-2+1時(shí)，f(Km∨Kn)=3. 設(shè)X為有向圖D的一個(gè)璜點(diǎn)集，如果X是一個(gè)獨(dú)立集并且X之外的每一個(gè)點(diǎn)都能經(jīng)一步或兩步到達(dá)X，則X稱為D的一個(gè)擬核.本文我們給出了有向圖中有一對(duì)不相交的擬核的一個(gè)必要條件和若干充分條件. 點(diǎn)v的離心距e(v)是D中v到其它所有點(diǎn)的最大距離.若dD(v，u)=e(v)，則點(diǎn)u是點(diǎn)v的離心點(diǎn).有向圖D的離心有向圖ED(D)與D有相同的頂點(diǎn)集且它的弧集定義