运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2014年
3期
104-110
,共7页
Alcuin数%横贯%独立集
Alcuin數%橫貫%獨立集
Alcuin수%횡관%독립집
Alcuin number%transversal set%independent set
1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等考虑了一般“冲突图”上的渡河问题.将这一问题推广到超图H=(V,ε)上,考虑一类情况更一般的运输计划问题.现在监管者欲运输超图中的所有点(代表“items”)渡河,这里V的点子集形成超边当且仅当这些点代表的“items”在无人监管的情况下不能留在一起.超图H的Alcuin数是指超图H具有可行运输方案(即把V的点代表的“items”全部运到河对岸)时船的最小容量.给出了r-一致完全二部超图和它的伴随超图,以及r-一致超图的Alcuin数,同时证明了判断r-一致超图是否为小船图是NP-困难的.
1000多年前,英國著名學者Alcuin曾提齣過一箇古老的渡河問題,即狼、羊和捲心菜的渡河問題.最近,Prisner和Csorba等攷慮瞭一般“遲突圖”上的渡河問題.將這一問題推廣到超圖H=(V,ε)上,攷慮一類情況更一般的運輸計劃問題.現在鑑管者欲運輸超圖中的所有點(代錶“items”)渡河,這裏V的點子集形成超邊噹且僅噹這些點代錶的“items”在無人鑑管的情況下不能留在一起.超圖H的Alcuin數是指超圖H具有可行運輸方案(即把V的點代錶的“items”全部運到河對岸)時船的最小容量.給齣瞭r-一緻完全二部超圖和它的伴隨超圖,以及r-一緻超圖的Alcuin數,同時證明瞭判斷r-一緻超圖是否為小船圖是NP-睏難的.
1000다년전,영국저명학자Alcuin증제출과일개고로적도하문제,즉랑、양화권심채적도하문제.최근,Prisner화Csorba등고필료일반“충돌도”상적도하문제.장저일문제추엄도초도H=(V,ε)상,고필일류정황경일반적운수계화문제.현재감관자욕운수초도중적소유점(대표“items”)도하,저리V적점자집형성초변당차부당저사점대표적“items”재무인감관적정황하불능류재일기.초도H적Alcuin수시지초도H구유가행운수방안(즉파V적점대표적“items”전부운도하대안)시선적최소용량.급출료r-일치완전이부초도화타적반수초도,이급r-일치초도적Alcuin수,동시증명료판단r-일치초도시부위소선도시NP-곤난적.
