簡單圖

簡單圖

無向圖中,關聯一對頂點的無向邊如果多於1條,則稱這些邊為平行邊,平行邊的條數稱為重數。在有向圖中,關聯一對頂點的有向邊如果多於1條,並且這些邊的始點與終點相同(也就是它們的的方向相同),稱這些邊為平行邊。含平行邊的圖稱為多重圖,既不含平行邊也不包含自環的圖稱為簡單圖。

基本介紹

  • 中文名:簡單圖
  • 外文名:Simple graph
  • 定義:既不含平行邊也不含自環的圖
  • 表達式:G(V,E)
  • 所屬學科:數學
定義,幾種簡單圖舉例,完全無向圖,補圖,相關知識點,

定義

設G=(V,E)是圖,若G中既無吊環又無多重邊,則稱G是簡單圖(simplegraph),如下圖,圖1是簡單圖,圖2是彼得森(Petersen,1831—1910)圖,它是一個有著特殊性質的簡單圖,一種妖怪圖(snark graph)。
圖1圖1
圖2圖2

幾種簡單圖舉例

完全無向圖

是n階簡單無向圖,若G中任意節點都與其餘n一1個節點鄰接,則稱G為n階完全無向圖(Complete Graph),記為
圖3所示分別是
圖3圖3
將n階完全無向圖
的邊任意加一個方向所得到的有向圖稱為n階競賽圖
是n階簡單有向圖,若G中任意節點都與其餘n-1個節點鄰接,則稱G為n階完全有向圖。顯然,n階完全有向圖
的任意兩個節點都是相互鄰接的,其邊是成對出現的。容易證明,n階完全無向圖
的邊數為

補圖

是n階簡單無向圖,由G的所有節點以及由能使G成為
需要添加的邊構成的圖稱為G的補圖,記為
如圖4所示的圖互為補圖,它們是相對於完全圖而言的。
圖4圖4
顯然,對於任意節點u和v,若u和v在G中不鄰接,則u和v在
中鄰接,若u和v在G中鄰接,則u和v在
中不鄰接。

相關知識點

圖G(graph)主要由如下兩部分組成。
(1)節點集合V,其中的元素v稱為節點(vertex或node);
(2)邊集合E,其中的元素稱為(edge)。
通常將圖G記為
,一個圖是一個集合上的一種二元關係,這個集合的元素稱為圖的節點,若兩節點之間有這種確定的二元關係,則稱有一條邊連這兩個節點,一個圖的節點的數目稱為這個圖的;圖的邊的數目稱為它的度。在文獻中,總是將一般的圖記為
,其中,
分別表示G的節點集和邊集。
需要說明的是:
①節點又可以稱為點、頂點或結點,常用一個實心點或空心點表示,但在實際套用中還可以用諸如方形、圓形、菱形等符號,為了方便可以在這些符號的旁邊或內部寫上表意名稱,如圖5所示是一個典型的貝葉斯網路(Bayesian networks)。
圖5圖5
②邊及其的表示.在圖6中的邊如
是沒有方向的,稱為無向邊,可以認為A是起點B是終點,也可以認為B是起點A是終點,這時A和B稱為邊
的端點(endvertices),在不致混淆時可將邊
,簡記為AB、BA、{A,B}或{B,A},表示邊的集合{A,B}={B,A}中的兩元素可以相同,是可重集合,與通常的集合有所不同.有方向的邊,稱為有向邊或弧(arc)。
圖6圖6
所有邊都是無向邊的圖稱為無向圖(graph或undirected graph),所有邊都是有向邊的圖稱為有向圖(digraph或directed graph)。
③圖的拓撲不變性質。需要注意的是,我們討論的圖不但與節點位置無關,而且與邊的形狀和長短也無關。
若有一條邊連一個圖的某兩個節點,則稱這兩個節點相鄰,並稱這兩個節點為這條邊的端點;若某一節點是某一條邊的端點,則稱這個節點和這條邊關聯;若兩條邊和同一節點關聯,則稱這兩條邊相鄰;兩個端點是同一個節點的邊稱為;若某條邊的兩個端點不是同一個節點,且只有一條邊連這兩個節點,則稱這條邊為
只有一個節點而沒有邊的圖稱為平凡圖;沒有邊的圖稱為孤立圖;以某兩節點為端點的邊可能不止一條,這時稱連這兩個節點的邊為重邊,既可以有環,也可以有重邊的圖稱為準圖;沒有環而可能有重邊的圖稱為帶重圖;沒有重邊而可能有環的圖稱為帶環圖;既沒有重邊也沒有自環的圖稱為簡單圖;若一個圖的階是有限的,則稱這個圖為有限圖,否則稱這個圖為無限圖;每兩個節點都相鄰的簡單圖稱為完全圖;若一個n階圖的節點用1,2,…,n來代表,則稱它為標定圖;若在圖的每一條邊上賦以一個實數或者對於每個節點賦以一個實數,則稱它為賦權圖

相關詞條

熱門詞條

聯絡我們