自反性：（都自指）所有的點(diǎn)自己指向自己【<a,a><b,b>】；
反自反性：（都不自指）所有的點(diǎn)都絕不自己指向自己；
對稱性：但凡指，定互指【<a,b>,<b,a>】；
反對稱性：但凡指，定單指；
傳遞性：間接指向，定直指【<a,b><b,c><a,c>】；

?

【平面圖 】
*|歐拉公式：
1個(gè)聯(lián)通分支：
頂點(diǎn)數(shù) - 邊數(shù) + 面數(shù) = 1 + 1
推廣到n個(gè)聯(lián)通分支：
頂點(diǎn)數(shù) - 邊數(shù) + 面數(shù) = 聯(lián)通分支數(shù) + 1?
*|握手定理對偶
平面圖所有面的次數(shù)和 = 2 x 邊數(shù)

?

如果A，就B.?
如果A，則B. <=>
A僅當(dāng)B.<=>A->B
】
只有A，才有B.
除非A，才有B.<=>
B->A
】
除非A，否則B<=>
(┒A)->B
】
A當(dāng)且僅當(dāng)B<=>
A<=>B 樹的度數(shù)之和 = 2 x 邊數(shù)?
例題：
若一棵樹有兩個(gè)2 度頂點(diǎn)，一個(gè)3度頂點(diǎn)，3個(gè)4 度頂點(diǎn)，其余都有是樹葉，則該樹共有 15 個(gè)頂點(diǎn)
假設(shè)有n個(gè)定點(diǎn)，邊數(shù)為n-1;則
（4+3+12+n-6）= 2 x（n-1） 取模運(yùn)算：a % p（或a mod p），表示a除以p的余數(shù)。
模p加法：(a + b) % p = (a % p + b % p) % p ，其結(jié)果是a+b算術(shù)和除以p的余數(shù)。
模p減法：(a - b) % p = (a % p - b % p) % p，其結(jié)果是a-b算術(shù)差除以p的余數(shù)。
模p乘法： (a * b) % p = (a % p * b % p) % p，其結(jié)果是 a * b算術(shù)乘法除以p的余數(shù)。?
結(jié)合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p?
((a*b) % p * c)% p = (a * (b*c) % p) % p?
交換律：
(a + b) % p = (b+a) % p?
(a * b) % p = (b * a) % p?
分配律：
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p 設(shè)G為群,a∈G,
若存在a^(k)=e成立的最小正整數(shù)k成為a的階(或周期)記作|a|=k,也稱a為k階元;?
若不存在這種k，則稱a為無限階元；
【】
例題：
設(shè)G為群,a,b,cG,證明:|abc|=|bca|=|cab|
證明：
設(shè)|abc|=t ; |bca|=n ; |cab|=s ;
(abc)^(n+1)=abc……abc=a (bca)^(n) bc=aebc=abc;
最左與最右同時(shí)少abc得
∴(abc)^n=e；
t|n
同理可證n|t ，則t=n
同理可證n=s
∴|abc|=|bca|=|cab| 【歐拉通路】通過所有邊且僅一次行遍所有頂點(diǎn)的通路；
【歐拉回路】通過所有邊且僅一次行遍所有頂點(diǎn)的回路；
【歐拉圖】具有【歐拉回路】的圖；
【半歐拉圖】具有【歐拉通路】而無【歐拉回路】的圖；
1.無向連通圖G是【歐拉圖】<=>G不含奇數(shù)度結(jié)點(diǎn)(G的所有結(jié)點(diǎn)度數(shù)為偶數(shù))；
&1.1無向圖G是【歐拉圖】<=>G連通的且不含奇數(shù)度結(jié)點(diǎn)
2.無向連通圖G是【半歐拉圖】<=>G有零個(gè)或兩個(gè)奇數(shù)度的結(jié)點(diǎn)；
&2.2無向圖G是【半歐拉圖】<=>G是連通的有零個(gè)或兩個(gè)奇數(shù)度的結(jié)點(diǎn)；
&3.有向圖D是【歐拉圖】<=>D圖是強(qiáng)連通的且D中每個(gè)結(jié)點(diǎn)的【入度=出度】
&4.有向圖D含有【半歐拉圖】<=>D圖為單向連通的且D中除兩個(gè)結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)的入度=出度，且此兩點(diǎn)滿足deg－(u)－deg+(v)=±1。（起始點(diǎn)s的入度=出度-1，結(jié)束點(diǎn)t的出度=入度-1 或兩個(gè)點(diǎn)的入度=出度）
5.一個(gè)非平凡連通圖是歐拉圖當(dāng)且僅當(dāng)它的每條邊屬于奇數(shù)個(gè)環(huán)。
&5.5G是非平凡的歐拉圖<=>G是連通的且是若干個(gè)邊不重的圈的并。
6.如果圖G是歐拉圖且 H = G - uv，則H有奇數(shù)個(gè)u,v-跡僅在最后訪問v；同時(shí)，在這一序列的u,v-跡中，不是路徑的跡的條數(shù)是偶數(shù)。(Todia[1973]) S×S={<2,2><2,3>,<2,4>,<3,2>,<3,3>,<3,4>,<4,2>,<4,3>,<4,4>}
<a,b>R<c,d>＜＝＞a-d＝c-b＜＝＞a+b=c+d，兩個(gè)有序?qū)χ灰獌蓚€(gè)元素和相等就具有關(guān)系R，所以R很明顯滿足
自反性：<a,b>∈SxS,a+b=a+b＜＝＞<a,b>R<a,b>
對稱性:<a,b><c,d>∈SxS,<a,b>R<c,d>＜＝＞a+b=c+d＜＝＞<c,d>R<a,b>
傳遞性:<a,b><c,d><e,f>∈SxS,,<a,b>R<c,d>∧<c,d>R<e,f>＜＝＞a+b=c+d=e+f＜＝＞<a,b>R<e,f>
所以R是等價(jià)關(guān)系。
根據(jù)R的定義，只要兩個(gè)有序?qū)Φ膬蓚€(gè)元素的和相等，兩個(gè)有序?qū)驮谕粋€(gè)等價(jià)類中。S×S中的有序?qū)Φ膬蓚€(gè)元素的和只能是4,5,6,7,8。
和為4的有：<2,2>
和為5的有：<2,3>，<3,2>
和為6的有：<2,4>，<3,3>，<4,2>
和為7的有：<3,4>，<4,3>
和為8的有：<4,4>
所以商集A/R＝｛｛<2,2>｝，｛<2,3>，<3,2>｝，｛<2,4>，<3,3>，<4,2>｝，｛<3,4>，<4,3>｝，｛<4,4>｝｝ △(G)>n-1一定不可簡單圖化；用于排除
設(shè)G為仁義n階無向簡單圖，則△(G)≤n-1； 多重圖-有平行邊
簡單圖-不含平行邊且不含環(huán)


G為n階無向【簡單】圖，若G中每個(gè)頂點(diǎn)均與其余的n-1個(gè)定點(diǎn)相鄰，則成G為n階無向完全圖，簡稱n階完全圖，及作Kn（n≥1）


設(shè)D為n階有向【簡單】圖，若D的基圖為n階無向完全圖Kn，則稱D是n階【競賽】圖


設(shè)G為n階無向【簡單】圖，若任意點(diǎn)v∈V（G），均有d（v）=k，則稱G為k-正則圖?


G與G‘ ，同時(shí)為有（無）向圖 ，
V'包含于V且E'包含于E ，則G‘是G的子圖，G是G’的母圖；
V'真包含于V或E'真包含于E ，則G‘是G的真子圖；
點(diǎn)集V‘=V，G’是G的生成子圖 G=<V,E>,則(非G)=<V,ē>是G的【補(bǔ)圖】
當(dāng)G≌(非G)，則成G是【自補(bǔ)圖】 k(G)點(diǎn)連通度=min{|V'| |V'為G的點(diǎn)割集}；
非連通圖k(G)=0；
kk-連通圖k(G)=kk(kk>=1)


λ(G)邊連通度=min{|E'| |E'為G的邊割集}
非連通圖 λ(G)=0；
n-邊連通圖 λ(G)=n(n>=1)


任何無向圖G，有k(G)≤λ(G)≤最小度δ(G) 二部圖(二部圖，二分圖，偶圖)
任意e（e∈E->e的兩個(gè)端點(diǎn)v∈V1,v'∈V2）


V1每個(gè)頂點(diǎn)均與V2所有頂點(diǎn)相鄰，則G是完全二部圖
記作Kr,s?
r=|V1|;s=|V2|;


n階零圖為二部圖；


n(≥2)j階無向圖G是二部圖<=>G中無奇圈 【平面圖】
完全圖K5（五角星） 和完全二分圖K3,3 是【極小非平面圖】.


【極大平面圖】是【連通】的，并且階數(shù)n≥3時(shí)，沒有割點(diǎn)和橋


設(shè)G是n（n≥3）階【簡單連通】的平面圖，G為【極大平面圖】<=>G的每個(gè)面的次數(shù)均為3.


一個(gè)連通分支：
設(shè)G是連通的平面圖，且每個(gè)面的次數(shù)至少為l (l≥3)，則G的邊數(shù)m與頂點(diǎn)數(shù)n有 m≤l*(n-2)/(l-2)
推廣到k個(gè)連通分支：?
m≤l*(n-k-1)/(l-2)


設(shè)G是n(≥3)階m條邊的【簡單平面圖】，則 m≤3n-6 (邊數(shù)≤3x點(diǎn)數(shù)-6)


設(shè)G是n(≥3)階m條邊的【極大平面圖】，則m=3n-6 (邊數(shù)=3x點(diǎn)數(shù)-6)


設(shè)G是【簡單平面圖】，則G的最小度δ≤5 任意二部圖r、s，當(dāng)s≥1+r不是哈密頓圖


完全二部圖Kr,r都是哈密頓圖


完全二部圖Kr,r+1都是半哈密頓圖

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/xujiayu/p/4875930.html

總結(jié)

以上是生活随笔為你收集整理的离散数学A的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。