【正文】 為弱分圖 。 定義 在簡單有向圖 G中，若 G中任何兩個結(jié)點間都是可達的，則稱 G是強連通的；若任何兩個結(jié)點間至少是從一個結(jié)點可達另一個結(jié)點，則稱 G是單向連通的；若有向圖 G不是單向連通的，但其基礎(chǔ)圖是連通的，則稱 G是弱連通的。 對于有向圖而言 ， 結(jié)點間的可達性不再是等價關(guān)系 ， 它僅僅是自反的和傳遞的 。 定理 一個連通無向圖 G中的結(jié)點 v是割點 ?存在兩個結(jié)點 u和 w， 使得聯(lián)結(jié) u和 w的每條鏈都經(jīng)過 v。于是 ， 對于分離圖 G， ?(G)=0；對于存在割點的連通圖 G， ?(G)=1。若ω(GS)＞ ω(G)，但 ?T?S有 ?(GT)=?(G)，則稱 S是 G的一個分離結(jié)點集。 在圖的研究中 ， 常常需要考慮刪去與增加結(jié)點 、結(jié)點集 、 邊和邊集 （ 或弧集 ） 的問題 。 為完全起見 ， 規(guī)定每個結(jié)點到其自身是可達的 。 定理 在一個圖中 ， 若從結(jié)點 vi到結(jié)點 vj存在一條鏈 (或路 )， 則必有一條從 vi到 vj的基本鏈 (或基本路 )。 定義 在一條鏈 (或路 )中，若出現(xiàn)的邊 (或弧 )都是不相同的，稱該鏈 (或路 )為簡單鏈(或簡單路 )；若出現(xiàn)的結(jié)點都是不相同的，稱該鏈 (或路 )為基本鏈 (或基本路 )。 定義 給定無向圖 (或有向圖 )G=V， E。 滿足上述三個條件，然而并不同構(gòu)。 一般說來 ， 證明兩個圖是同構(gòu)的并非是輕而易舉的事情 ， 往往需要花些氣力 。 若存在雙射 f∈ V2V1， 使得對任意 v，u∈ V1， 有 〔 u， v〕 ∈ E1?〔 f(u)， f(v)〕 ∈ E2(或 u，v∈ E1f(u)， f(v)∈ E2)則稱 G1同構(gòu)于 G2， 記為 G1?G2。 在圖的定義中 ， 強調(diào)的是結(jié)點集 、 邊集以及邊與結(jié)點的關(guān)聯(lián)關(guān)系 ， 既沒有涉及到聯(lián)結(jié)兩個結(jié)點的邊的長度 、 形狀和位置 ， 也沒有給出結(jié)點的位置或者規(guī)定任何次序 。 定義 設(shè)圖 G1=V1， E1和圖G2=V2， E2是圖 G=V， E的子圖 。 (2) 如果 V2?V1， E2?E1且 E2≠E1， 則稱 G2為 G1的真子圖 ， 記為 G2?G1。 定理 給定無向圖 G=V， E，則 定理 在任何無向圖中，奇度結(jié)點的數(shù)目為偶數(shù)。 若 v點有環(huán) ， 規(guī)定該點度因環(huán)而增加 2。 顯然 ， 在零圖中邊集為空集 。 定義 在無向圖 G=V， E中 ， 如果 V中的每個結(jié)點都與其余的所有結(jié)點鄰接 ， 即 (?vi)(?vj)(vi， vj∈ V→ 〔 vi， vj〕 ∈ E) 則該圖稱為無向完全圖 ， 記作 K|V|。 定義 在圖 G=V， E中，如果每條邊都是弧，該圖稱為有向圖；若每條邊都是無向邊，該圖 G稱為無向圖；如果有些邊是有向邊，另一些邊是無向邊，圖 G稱為混合圖。關(guān)聯(lián)同一個結(jié)點的兩條邊或弧稱為鄰接邊或弧。其中 V是個非空有限集合，它的元素稱為結(jié)點； E也是個有限集合，其元素稱為邊，而 φ是從 E到 V中的有序?qū)驘o序?qū)Φ挠成洹５谑? 圖的概念與表示 圖的基本概念 鏈 (或路 )與圈 (或回路 ) 圖的矩陣表示 退出 圖的基本概念 什么是圖 ?可用一句話概括 ， 即：圖是用點和線來刻劃離散事物集合中的每對事物間以某種方式相聯(lián)系的數(shù)學模型 。 定義 一個圖 G定義為一個三元組 V，E， φ，記作 G=V， E， φ。 若結(jié)點 vi與 vj由一條邊 (或弧 )e所聯(lián)結(jié)，則稱結(jié)點 vi和 vj是邊 (或弧 )e的端結(jié)點；同時也稱結(jié)點vi與 vj是鄰接結(jié)點，記作 vi adj vj；否則為非鄰接結(jié)點，記作 vi nadj vj；也說邊 (或弧 )e關(guān)聯(lián) vi與 vj或說結(jié)點 vi與 vj關(guān)聯(lián)邊 (或弧 )e。 如果把圖 G中的弧或邊總看作聯(lián)結(jié)兩個結(jié)點，則圖 G可簡記為 G=V， E，其中 V是非空結(jié)點集， E是聯(lián)結(jié)結(jié)點的邊集或弧集。 加權(quán)圖在實際中有許多應用 ， 如在輸油管系統(tǒng)圖中權(quán)表示單位時間流經(jīng)管中的石油數(shù)量；在城市街道中 ，權(quán)表示表示通行車輛密度；在航空交通圖中 ， 權(quán)表示兩城市的距離等等 。僅有孤立結(jié)點的圖稱為零圖 。 對于無向圖 G=V， E， 結(jié)點 v∈ V的度數(shù)等于聯(lián)結(jié)它的邊數(shù) ， 也記為 d(v)。 關(guān)于無向圖中的結(jié)點的度，歐拉給出一個定理，這是圖論中的第一個定理。 定義 給定無向圖 G1=V1， E1和 G2=V2，E2， 于是 (1) 如果 V2?V1和 E2?E1， 則稱 G2為 G1的子圖 ， 記為 G2?G1。 若對任意結(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〕 。 顯然 ， G與 互為補圖 。 定義 給定無向圖 (或有向圖 )G1=V1， E1和 G2=V2， E2。對于有向圖的同構(gòu)還要求保持邊的方向 。 但這僅僅是必要條件而不是充分條件。 例如圖 (a)與 (b)