【正文】 第十六章 圖的概念與表示 圖的基本概念 鏈 (或路 )與圈 (或回路 ) 圖的矩陣表示 退出 圖的基本概念 什么是圖 ?可用一句話概括 ， 即：圖是用點和線來刻劃離散事物集合中的每對事物間以某種方式相聯(lián)系的數(shù)學模型 。 因為它顯得太抽象 ， 不便于理解 ， 所以有必要給出另外的回答 。 下面便是把圖作為代數(shù)結(jié)構(gòu)的一個定義 。 定義 一個圖 G定義為一個三元組 V，E， φ，記作 G=V， E， φ。其中 V是個非空有限集合，它的元素稱為結(jié)點； E也是個有限集合，其元素稱為邊，而 φ是從 E到 V中的有序?qū)驘o序?qū)Φ挠成洹? 由定義可知，圖 G中的每條邊都與圖中的無序或有序結(jié)點對相聯(lián)系的。若邊 e∈ E與無序結(jié)點對 〔 vi， vj〕 相聯(lián)系，則 φ(e)=〔 vi， vj〕 ，這時邊 e稱為無向邊，有時簡稱為邊；若邊 e∈ E與有序結(jié)點對 vi， vj相聯(lián)系，則 φ(e)=vi， vj，此時邊 e稱為有向邊或弧， vi稱為弧 e的始結(jié)點，vj稱為弧 e的終結(jié)點。 若結(jié)點 vi與 vj由一條邊 (或弧 )e所聯(lián)結(jié)，則稱結(jié)點 vi和 vj是邊 (或弧 )e的端結(jié)點；同時也稱結(jié)點vi與 vj是鄰接結(jié)點，記作 vi adj vj；否則為非鄰接結(jié)點，記作 vi nadj vj；也說邊 (或弧 )e關聯(lián) vi與 vj或說結(jié)點 vi與 vj關聯(lián)邊 (或弧 )e。關聯(lián)同一個結(jié)點的兩條邊或弧稱為鄰接邊或弧。而聯(lián)結(jié)一結(jié)點與它自身的一條邊，稱為環(huán)。環(huán)的方向是無意義的。 如果把圖 G中的弧或邊總看作聯(lián)結(jié)兩個結(jié)點，則圖 G可簡記為 G=V， E，其中 V是非空結(jié)點集， E是聯(lián)結(jié)結(jié)點的邊集或弧集。 定義 在圖 G=V， E中，如果每條邊都是弧，該圖稱為有向圖；若每條邊都是無向邊，該圖 G稱為無向圖；如果有些邊是有向邊，另一些邊是無向邊，圖 G稱為混合圖。 定義 在圖 G=V， E中 ， 如果任何兩結(jié)點間不多于一條邊 (對于有向圖中 ， 任何兩結(jié)點間不多于一條同向弧 )， 并且任何結(jié)點無環(huán) ， 則圖 G稱為簡單圖；若兩結(jié)點間多于一條邊 (對于有向圖中 ， 兩結(jié)點間多于一條同向弧 )圖 G稱為多重圖 ， 并把聯(lián)結(jié)兩結(jié)點之間的多條邊或弧 ， 稱為平行邊或弧 ， 平行邊或弧的條數(shù)稱為重數(shù) 。 定義 給每條邊或弧都賦予權的圖 G=V，E， 稱為加權圖 ， 記為 G=V， E， W， 其中 W表示各邊之權的集合 。 加權圖在實際中有許多應用 ， 如在輸油管系統(tǒng)圖中權表示單位時間流經(jīng)管中的石油數(shù)量；在城市街道中 ，權表示表示通行車輛密度；在航空交通圖中 ， 權表示兩城市的距離等等 。 定義 在無向圖 G=V， E中 ， 如果 V中的每個結(jié)點都與其余的所有結(jié)點鄰接 ， 即 (?vi)(?vj)(vi， vj∈ V→ 〔 vi， vj〕 ∈ E) 則該圖稱為無向完全圖 ， 記作 K|V|。 若|V|=n， 該圖記作 Kn。 在一個圖中 ， 如果一個結(jié)點不與任何其他結(jié)點鄰接 ， 則該結(jié)點稱為孤立結(jié)點 。僅有孤立結(jié)點的圖稱為零圖 。 顯然 ， 在零圖中邊集為空集 。 若一個圖中只含一個孤立結(jié)點 ， 該圖稱為平凡圖 。 定義 在有向圖 G=V， E中 ， 對任意結(jié)點v∈ V， 以 v為始結(jié)點的弧的條數(shù) ， 稱為結(jié)點 v的出度 ， 記為 d+(v)；以 v為終結(jié)點的弧的條條數(shù) ， 稱為 v的入度 ， 記作 d(v)；結(jié)點 v的出度與入度之和 ， 稱為結(jié)點的度數(shù) ，記為 d(v)， 顯然 d(v)=d+(v)+d(v)。 對于無向圖 G=V， E， 結(jié)點 v∈ V的度數(shù)等于聯(lián)結(jié)它的邊數(shù) ， 也記為 d(v)。 若 v點有環(huán) ， 規(guī)定該點度因環(huán)而增加 2。 顯然，對于孤立結(jié)點的度數(shù)為零。 此外，對于無向圖 G=V， E，記 Δ(G)或 Δ=max{d(v)|v∈ V} δ(G)或 δ=min{d(v)|v∈ V} 它們分別稱為圖 G的最大度和最小度。 關于無向圖中的結(jié)點的度，歐拉給出一個定理，這是圖論中的第一個定理。 定理 給定無向圖 G=V， E，則 定理 在任何無向圖中，奇度結(jié)點的數(shù)目為偶數(shù)。 定義 在無向圖 G=V， E中 ， 如果每個結(jié)點的度是 k， 即 (?v)(v∈ V→ d(v)=k)， 則圖 G稱為 k度正則圖 。 顯然 ， 對于 k度正則圖 G， Δ(G)=δ(G)=k。 定義 給定無向圖 G1=V1， E1和 G2=V2，E2， 于是 (1) 如果 V2?V1和 E2?E1， 則稱 G2為 G1的子圖 ， 記為 G2?G1。 (2) 如果 V2?V1， E2?E1且 E2≠E1， 則稱 G2為 G1的真子圖 ， 記為 G2?G1。 (3) 如果 V2=V1， E2?E1， 則稱 G2為 G1的生成子圖 ，記為 G2 G1。 定義 設圖 G2=V2， E2是圖 G1=V1， E1的子圖 。 若對任意結(jié)點 u和 v， 如果 〔 u， v〕 ∈ E1， 有 〔 u，v〕 ∈ E2， 則 G2由 V2唯一地確定 ， 并稱 G2是結(jié)點集合 V2的誘導子圖 ， 記作 V2或 G〔 V2〕 ；如果 G2無孤立結(jié)點 ，且由 E2所唯一確定 ， 則稱 G2是邊集 E2的誘導子圖 ， 記為E2或 G〔 E2〕 。 定義 設圖 G1=V1， E1和圖G2=V2， E2是圖 G=V， E的子圖 。 如果 E2=EE1且 G2=E2， 則稱圖 G2是相對于圖 G的子圖 G1的補圖 。 定義 給定圖 G=V， E， 若存在圖G1=V， E1， 并且 E1∩E=?和圖 V， E1∪ E是完全圖 ， 則 G1稱為相對于完全圖的 G的補圖 ，簡稱 G1是 G的補圖 ， 并記為 G1= 。 顯然 ， G與 互為補圖 。