有向圖的核理論.pdf

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

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

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