图论入门及基础概念（图篇）
目錄
- 目錄
- 圖篇
- 圖及其表示
- 圖論起源之七橋問題
- 圖論引入
- 圖的表示:
- 邊的表示和讀取：
- 點的表示和讀取：
- 圖論的基本概念
- 圖的表示引入
- 額。。。。 V3 = 。。。
- 圖的表示法
- 結語
圖篇
這是第一次寫博客，為了下載積分而來。
隨便寫些，各位大佬們多多指。
本次內容是關于圖論的引入的，內容如下：
- 矩陣引入
- 什么是圖？其如何表示？
- 圖論起源之七橋問題
- 圖論引入
- 圖論相關基本概念
- 圖論的表示引入
- 圖的表示法
- 矩陣引入
線性代數學的好的可以直接跳過，
當然，看不懂的也可以直接跳過，這部分引入只是計為了后面計算上方便，
首先，用向量描述一個物體必須先劃分維度。
由于原子守恒原理我們知道氧原子和氫原子相互獨立，互不相關。
所以我們假設兩個維度空間為氧空間和氫空間
并且這兩個空間相互垂直（即線性無關）
基于空間運算的封閉性，我們得出該方程式存在的完備空間S為：
由于向量空間運算的封閉性，我們有：
我們分別將氧氣和氫氣表示為該空間下的向量點：
于是化學方程式配平便變成了向量之間的運算：
由于氧氣和氫氣是該完備空間的基，即單質。
容易運算出答案：
圖及其表示
什么是 圖
要說什么是圖，這個有點不太好說，概念的東西太抽象，我還是直接說圖的表示吧，知道圖的表示形式，自然也就知道什么是圖了。
·圖的表示一般是分為兩塊的：
（1）某類具體事物
（2）這些事物之間的聯系
·而在圖論中，只存在兩種形態：
①節點
②邊
這兩種形態通常這樣對應：
由于這種對應關系，我們通常把這種關系轉化為矩陣描述，在前言中我們提到了一個例子：
在這里，具體事物即：
抽象事物（事物間的聯系）即其中的數量關系。
于是我們將化學方程改為如下矩陣式：
我們可以看到，矩陣分為兩塊：
PS: 所以說，用矩陣描述問題能使描述過程更加清晰化，建議采用。
圖論起源之七橋問題
七橋問題很經典，我們都知道大數學家歐拉將其轉為一筆畫的問題，并順利解決，由此開創了圖論的先河。
用下圖舉個例子：
若將其看做畫線問題：
對于任意非起始點，我們要一筆通過他只有如下兩種可能：
(1)兩條路線：
有進必有出，必然是能夠一筆完成的
(2)四條路線：
由于通過外界一圈以后又回來所以對于這種偶數條線路，
可以等效為如下形式：
即將該節點視為另外一個圈起始點，其中的閉圈必然能夠由一筆畫完成，由于該圈可以獨立出去，我們將該圈等效為不存在，便將偶數邊節點等效為如下一進一出的兩條邊節點:
三條路線：
三條線路相對復雜，但它的進出也只有如下兩種可能形式：
同樣，我們運用等效原理將其等效為如下形式：
我們將其中的閉圈化簡去掉，即等效為：
所以，該節點必然是一筆畫的起點（右圖形式）或者終點（左圖形式）
所以，我們得出了如下的基本結論：
①擁有偶數邊的節點
可以等效為只有一進一出兩條邊的點。
即該點等效為過程點。
②擁有奇數邊的節點
可以等效為要么進，要么出的單邊的節點。
即該點等效為起始點。
唧唧歪歪了這么多，我們還是回到七橋問題吧:
那么問題來了：
問：該圖能否由一筆畫完成，并說明理由。
首先我給出答案不能，理由是：
A、C、D、B節點均為奇數邊
故等效為4個起始點，而一個一筆畫的圖最多只能有兩個起始點。
PS:若要求一筆畫的終點和起點重合，則圖節點中必然全為偶數邊，這就是十分顯然的了。
圖論引入
圖論，顧名思義，必然是關于圖的理論咯
由于圖的表示分為兩塊：
①節點
②邊
我們不妨假設對于圖 ：
①節點集 記為:
，
② 邊集 記為:
那么問題來了：
我們該如何去表示其中的某個節點或邊呢？
PS：馬克思說：“人的本質不是單個人所固有的抽象物，在其現實性上，它是一切社會關系的總和。”（《馬克思恩格斯選集》第2版第1卷第60頁）
附即興打油詞一首：
《如果說》—妖米
如果說人類是一個集合，那么某個人便由他的社會關系總和來定義。
如果說節點集是一個集合，那么某個節點便由他的邊的總和來定義。
如果說邊集是一個集合，那么某條邊便由他連接的點的總和來定義。
2018-9-4 —— 23：12
圖的表示:
對于任意某條邊，以邊e1為例：
由于任意邊節點只有兩個，我們不妨記為
對于任意某個節點，分別以v3，v4為例：
對于v3，我們記為：
對于v4，我們記為：
但是，這么記雖然沒錯，但是我們想能不能用一種統一的格式去表示，將其任意點化為統一的標準格式
于是，我們靈光一閃想了一個辦法 ：
還記得前面提到的原子守恒那邊的完備空間吧
事實上，由于我們約定俗成，比如說第一行就表示v1，第二行就表示v2，所以我們完全可以將如上形式化為如下：
即以邏輯值來代表是否存在連接。
事實上，由于標準化的約定，我們可以將如上形式整理成表格：
| V1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| V2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| V3 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
| V4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
邊的表示和讀取：
點的表示和讀取：
由于如上表格中，既有包含所有點的表示，由包含所有邊的表示，所以那個表格便是一個圖。
通常我們不寫表格，主要原因麻煩，我們通常直接寫為矩陣：
圖論的基本概念
1、有向圖
顧名思義，就是有方向的圖唄。
2、無向圖
就是沒有有方向的圖唄，也可以叫雙向圖。像前面的例子，七橋問題都是無向圖。
3、有限圖
就是節點和邊都有限的圖唄。
4、簡單圖
就是沒有環和多重邊的圖，
因為環獨立且封閉，可產生自由變量，導致問題變復雜。多重邊可分解為 邊+環。
反例：
5、完全圖
就是任意兩個點都有一條邊相連的圖。
P s：有一種結構叫拓撲6、二分圖
可以把頂點集分成兩組，并且同組頂點不相鄰的圖。如：
7、子圖與母圖
如果原圖叫母圖，那么從其中摳一份下來，那就叫它的子圖。
8、頂點v的度：
就是頂點的邊數（環算兩條邊）。
由于每條邊都連接兩個頂點,所以一個圖的頂點度之和必然是邊的兩倍。
即：
任意圖必然可由N個1筆畫完成，而每一筆在圖中產生的奇頂點數要么2個，要么0個，所以任意圖的奇頂點數必然是偶數個，這是很顯然的。
9、 途徑
兩個頂點之間的通路我們稱為途徑。
若是途徑中沒有重復的頂點，我們稱為路。
如果沒有重復的邊，我們稱為跡。
10、邊與弧
為了區分邊是否有方向，通常
有方向的叫弧，沒方向的叫邊。
圖的表示引入
前面我們以七橋問題（無向圖）講了圖的表示：
| V1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| V2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| V3 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
| V4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
那么問題來了，用這種方式表示有向圖該怎么表示？
對于一個圖，有兩個要素：
1、具體要素
2、具體要素間的聯系
由于具體要素（頂點集）肯定沒法變：
①節點集 記為:
②弧集 記為:
我們嘗試另外一種表示：
我們不再用連接的邊來定義節點，而用鄰接節點來定義節點。如：
以下圖為例：
（可達的通路）的記為1。
額。。。。 V3 = 。。。
我們還是以下圖為例吧:
剛才你們什么都沒看見：
其中（可達的通路）的記為1。
于是我們整理成矩陣表格：
| V1 | ０ | １ | １ | ０ |
| V2 | ０ | ０ | １ | 0 |
| V3 | ０ | ０ | ０ | １ |
| V４ | １ | ０ | ０ | 0 |
我們做如下約定：
于是，該矩陣定義了頂點之間的聯系。
即表示出了弧集。
我們發現，這種矩陣定義的方式，既可以表示有向圖，又可以表示無向圖，而且貌似還比原來的表示方法更節省空間。
但是這種方法的缺點很明顯就是，當出現多重邊時無法表示，反正你們剛才什么都沒看到就對了。
圖的表示法
這種用鄰接節點定義其他節點的方法:
我們不妨叫做鄰接矩陣法：
而那種用邊將兩個頂點關聯起來的方法，
我們不妨叫關聯矩陣法：
事實上，我們用關聯矩陣也可以表示有向圖，只要約定入節點為-1，出節點為1即可。當然，還有其他方法可以表示圖，在計算機中，只要方便于運算的表示方法都可以。
如，直接用弧集來表示圖：
即用二維數組的方法表示。
這種用弧集表來表示圖的方法，
我們不妨叫弧表表示法
當然，還可以整理成有序的：
對了，忘了講一件事，
通常我們增加一行，用來放弧的權重。對于鄰接矩陣和關聯矩陣，直接把例中的１改成相應權重即可。
- 還有一種方法，就是用程序把圖畫出來。
熟悉C語言的童鞋可能知道指針和結構體。
如果接觸過數據結構可能知道鏈表。
如：
struct point
{
point * P;
int Data;
};
然后將數據掛在鏈表上。
這種方法提一下，懂的自然懂。
不懂也沒關系，反正我也不多講了。
結語
- 本次介紹了圖論相關基本概念以及相關表
- 感謝您的耐心閱讀
- 原創作品，如轉載，請注明出處
- 版權聲明：https://blog.csdn.net/qq_43133135/article/details/82390300
總結
以上是生活随笔為你收集整理的图论入门及基础概念（图篇）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【转】VS问题集合，不用也要收藏防止以后
- 下一篇： C#中的几个实用的代码