1.圖的定義
圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成,通常表示為:G(V,E),其實(shí),G表示一個圖,V是圖G中頂點(diǎn)的集合,E的圖G中邊的集合
線性表中我們把數(shù)據(jù)元素叫元素,樹中將數(shù)據(jù)元素叫結(jié)點(diǎn),在圖中數(shù)據(jù)元素,我們則稱為頂點(diǎn)
圖1
2.各種圖的定義
無向邊:若頂點(diǎn)Vi到Vj之間的邊沒有方向,則稱這條邊為無向邊,用無序偶對(Vi,Vj)來表示.如果圖中所有的邊都是無向邊,則稱該圖為無向圖,圖1就是典型的無向圖
有向邊:若頂點(diǎn)Vi到Vj之間的邊有方向,則稱這條邊為有向邊,也稱為弧.用有序偶對<Vi,Vj>來表示,如果圖中所有的邊都是有向邊,則稱該圖為有向圖**
有向圖
在無向圖中,如果任意兩個頂點(diǎn)之間都存在邊,則稱該圖為無向完全圖.含有n個頂點(diǎn)的無向完全圖有n(n-1)/2*條邊.
無向完全圖
在有向圖中,如果任意兩個頂點(diǎn)之間都存在方向互為相反的兩條弧,則稱該圖為有向完全圖.含有n個頂點(diǎn)的有向完全圖有n(n-1)*條邊
有向完全圖
與圖的邊或弧相關(guān)的數(shù)叫做權(quán).這些權(quán)可以表示從一個頂點(diǎn)到另一個頂點(diǎn)的距離或耗費(fèi).這種帶權(quán)的圖通常稱為網(wǎng)
權(quán)
假設(shè)有兩個圖G=(V,{E})和G2=(V2,{E2}),如果V2屬于V,且E2屬于E,我們稱G2為G的子圖
子圖
