有向圖的核理論.pdf

1、在過去的三十多年里，隨著計(jì)算機(jī)科學(xué)的迅速發(fā)展，圖論也得到了飛速發(fā)展，而圖論中發(fā)展最快的領(lǐng)域也許就是控制數(shù)理論的研究.有向圖的核作為眾多控制參數(shù)之一，由于它在現(xiàn)實(shí)世界中，例如博弈論、編碼理論、邏輯學(xué)、選址科學(xué)等理論與實(shí)踐中有著廣泛而深刻的應(yīng)用背景，受到了越來越多的研究人員的關(guān)注. 設(shè)圖D=(V,A)是無環(huán)無多重弧的有限有向圖，但是允許成對方向相反的弧存在.V和A分別為有向圖D的頂點(diǎn)集和弧集.設(shè)S(∈)V，若V-S中的每一個(gè)點(diǎn)均可通

2、過一條弧指向S中的一點(diǎn)，則稱S為D的吸收集.如果集合K(∈)V既是獨(dú)立集又是吸收集，則稱K為D的核.1944年，VonNeumann和Morgenstern在論述博弈論時(shí)介紹了有向圖核的概念，這個(gè)概念來源于分配和控制理論.1981年，Kwa(s)nik將核的概念推廣到了(k，l)-核上，其中k≥2，l≥1. 有向圖核理論的研究主要集中在各種有向圖類核的存在性上.然而，通過分析有向圖的結(jié)構(gòu)性質(zhì)來研究核的存在性不太容易.于是，人們從

3、另外一個(gè)角度進(jìn)行研究，發(fā)現(xiàn)了有向圖D及其線圖L(D)中半核(擬核)之間的關(guān)系.因此，仍有可能發(fā)現(xiàn)有向圖及其線圖中廣義核的關(guān)系.本文主要研究了有向圖及其線圖中的廣義核，主要工作分為兩個(gè)部分： 第一部分，我們證明了下述結(jié)果：有向圖D存在k-半核當(dāng)且僅當(dāng)其線圖L(D)中存在k-半核；D中k-半核的數(shù)目少于或等于L(D)中k-半核的數(shù)目；D中k-擬核的數(shù)目少于或等于L(D)中k-擬核的數(shù)目；D中k-核的數(shù)目等于L(D)中k-核的數(shù)目；刻