1、有向圖和無(wú)向圖    

有向圖是有方圖；所謂無(wú)向圖，沒(méi)有方向的圖

2、路徑和環(huán)

我們有經(jīng)過(guò)重復(fù)的點(diǎn)的路徑就叫做簡(jiǎn)單路徑。    

環(huán)的定義是在路徑的定義的基礎(chǔ)上做了一定的拓展，首尾相接的路徑我們就把它叫做一個(gè)環(huán)。同樣我們也有簡(jiǎn)單環(huán)，也就是除開首尾以外，剩下的部分不會(huì)經(jīng)過(guò)重復(fù)的點(diǎn)的環(huán)就叫做簡(jiǎn)單環(huán)。

3、極大獨(dú)立集

如果K是G的獨(dú)立集，且不是任何其他獨(dú)立集的真子集，就為極大獨(dú)立集。

4、極大團(tuán)

如果一個(gè)團(tuán)不被其他任一團(tuán)所包含，即它不是其他任一團(tuán)的真子集，則稱該團(tuán)為圖G的極大團(tuán)。

5、最大團(tuán)

頂點(diǎn)最多的極大團(tuán)，稱之為圖G的最大團(tuán)。

6、獨(dú)立集

獨(dú)立集是指圖G=(V,E)中兩兩互不相鄰的頂點(diǎn)構(gòu)成的集合。

參考資料：百度百科-圖論

-

下面是更多關(guān)于圖論的問(wèn)答

1向圖

一個(gè)無(wú)向圖U個(gè)二元組<N,E>，N是一個(gè)非空集合的記為N(U)，其中的元素是頂點(diǎn)或結(jié)點(diǎn)；E是無(wú)序積NxN的多重子集（元素可多次出現(xiàn)），是邊集，記為E(U)，其中的元素稱為無(wú)向邊或邊。

例如，N={n1,n2,n3,n4,n5},E={(n1,n2), (n2,n2), (n2,n3), (n1,n3), (n1,n4)}

2、有向圖

一個(gè)有向圖D是一個(gè)二元組<N,E>，N是一個(gè)非空集合點(diǎn)集，其中的元素是頂點(diǎn)或結(jié)點(diǎn)，記為N(D)；E是卡氏積的多重子集，記為E(D)，其元素稱為有向邊或邊或弧。

例如，N={n1,n2,n3,n4,n5},E={<n1,n1>,<n2,n3>,<n3,n2>,<n3,n4>,<n2,n4>,<n4,n5>,<n5,n4>,<n1,n2>}

3、混合圖

圖中有些邊是有向邊，另一些邊是無(wú)向邊。

4、鄰接集

給定一個(gè)無(wú)向圖U和圖中的一個(gè)結(jié)點(diǎn)ni，ni的鄰接集就是在圖中直接和ni相連的結(jié)點(diǎn)集合。根據(jù)有向邊描述的方向性，在有向圖中ni的鄰接集又可分為兩部分。

5、無(wú)向完全圖。

設(shè)G是n階無(wú)向簡(jiǎn)單圖，若G中任何頂點(diǎn)都與其余n-1個(gè)頂點(diǎn)相鄰，則G為n階無(wú)向完全圖。

參考資料：百度百科-圖論

本回答被網(wǎng)友采納 歐拉定理

邊e，節(jié)點(diǎn)v，面f

f+v-e=2;

歐拉圖

漢米爾頓圖

簡(jiǎn)單的說(shuō)論中的橋是 集合E的元素，稱為邊（或線）。

圖G=（V,E）是一個(gè)二元組（V,E）使得E&#8838;[V]的平方，所以E的元素是V的2-元子集。為了避免符號(hào)上的混淆，默認(rèn)V∩B=&#216;。集合V中的元素稱為圖G的定點(diǎn)（或節(jié)點(diǎn)、點(diǎn)），而集合E的元素稱為邊（或線）。通常，描繪一個(gè)圖的方法是把定點(diǎn)畫成一個(gè)小圓圈，如果相應(yīng)的頂點(diǎn)之間有一條邊，就用一條線連接這兩個(gè)小圓圈，如何繪制這些小圓圈和連線時(shí)無(wú)關(guān)緊要的，重要的是要正確體現(xiàn)哪些頂點(diǎn)對(duì)之間有邊，哪些頂點(diǎn)對(duì)之間沒(méi)有邊。

圖論本身是應(yīng)用數(shù)學(xué)的一部份，因此，歷史上圖論曾經(jīng)被好多位數(shù)學(xué)家各自獨(dú)立地建立過(guò)。關(guān)于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中，當(dāng)時(shí)考慮的原始問(wèn)題有很強(qiáng)的實(shí)際背景---遍歷"橋"問(wèn)題！在解答問(wèn)題的同時(shí)，開創(chuàng)了數(shù)學(xué)的一個(gè)新的分支——圖論與幾何拓?fù)洹?/p>

哥尼斯堡（今俄羅斯加里寧格勒）是東普魯士的首都，普萊格爾河橫貫其中。十八世紀(jì)在這條河上建有七座橋，將河中間的兩個(gè)島和河岸聯(lián)結(jié)起來(lái)。人們閑暇時(shí)經(jīng)常在這上邊散步，一天有人提出：能不能每座橋都只走一遍，最后又回到原來(lái)的位置。這個(gè)問(wèn)題看起來(lái)很簡(jiǎn)單有很有趣的問(wèn)題吸引了大家，很多人在嘗試各種各樣的走法，但誰(shuí)也沒(méi)有做到�？磥�(lái)要得到一個(gè)明確、理想的答案還不那么容易。

1736年，有人帶著這個(gè)問(wèn)題找到了當(dāng)時(shí)的大數(shù)學(xué)家歐拉，歐拉經(jīng)過(guò)一番思考，很快就用一種獨(dú)特的方法給出了解答。歐拉把這個(gè)問(wèn)題首先簡(jiǎn)化，他把兩座小島和河的兩岸分別看作四個(gè)點(diǎn)，而把七座橋看作這四個(gè)點(diǎn)之間的連線。那么這個(gè)問(wèn)題就簡(jiǎn)化成，能不能用一筆就把這個(gè)圖形畫出來(lái)。經(jīng)過(guò)進(jìn)一步的分析，歐拉得出結(jié)論－－不可能每座橋都走一遍，最后回到原來(lái)的位置。并且給出了所有能夠一筆畫出來(lái)的圖形所應(yīng)具有的條件。這是拓?fù)鋵W(xué)的“先聲”。

在拓?fù)鋵W(xué)的發(fā)展歷史中，還有一個(gè)著名而且重要的關(guān)于多面體的定理也和歐拉有關(guān)。這個(gè)定理內(nèi)容是：如果一個(gè)凸多面體的頂點(diǎn)數(shù)是v、棱數(shù)是e、面數(shù)是f，那么它們總有這樣的關(guān)系：f+v-e=2。

拓?fù)鋵W(xué)中，虧格的定義：群的虧格是它的任意凱萊圖的最小格。 簡(jiǎn)單來(lái)說(shuō)就是，任何一個(gè)頂點(diǎn)連接到它的弧最多兩個(gè)。 集：數(shù)學(xué)的的分支學(xué)科，研究是一般集合。集合論或集論是研究集由一堆抽象構(gòu)成的整體）的數(shù)學(xué)理論，包含集合、元素和成員關(guān)系等最基本數(shù)學(xué)概念。

圖論：圖論〔Graph Theory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。

離散數(shù)學(xué)：離散數(shù)學(xué)(Discrete mathematics)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。

三者都是數(shù)學(xué)的分支學(xué)科。 是指該面邊界邊的條數(shù)，當(dāng)然，如果該面的邊界含有橋，則該橋應(yīng)該算兩次。 圖的鄰接矩陣中超過(guò)一半的元素的0的話就叫做稀疏圖

Tags：圖論,圖論的基本概念有哪些？,圖論中橋的概念是什么

轉(zhuǎn)載：文章來(lái)自用戶投稿不代表本站觀點(diǎn)，如有侵權(quán)請(qǐng)聯(lián)系我們。