Graph_Theory离散数学、图论、双语.ppt

《Graph_Theory离散数学、图论、双语.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、GraphTheoryChapter1AnIntroductiontoGraphs大葉大學資訊工程系黃鈴玲Ch1-2Outline1.1Whatisagraph?1.2TheDegreeofaVertex1.3IsomorphicGraphs1.4Subgraphs1.5DegreeSequences1.6ConnectedGraphs1.7Cut-VerticesandBridges1.8Specialgraphs1.9DigraphsCh1-3GraphTheory的起源1736,Eulersolved

2、theKönigsbergBridgeProblem(七橋問題)Q:是否存在一種走法，可以走過每座橋一次，並回到起點？(Ch7Eulergraph)Ch1-4KönigsbergBridgeProblemAns:因為每次經過一個點，都需要從一條邊進入該點，再用另一條邊離開，所以經過每個點一次要使用掉一對邊。每個點上連接的邊數必須是偶數才行此種走法不存在ABCDQ:是否存在一種走法，可以走過每條邊一次，並回到起點？Ch1-5Anelementaryexampleofgraphs4students:

3、A,B,C,D4positions:FF,SC,W,BS四人各有喜好的工作：(如下圖，連線表示有興趣)ABCDFFSCWBSQ:Canallfourstudentsfindjobstheylike?Ans:No(Ch6Matching)Ch1-6DefinitionofagraphAgraphGisafinitenonemptysetV(G)ofvertices(alsocallednodes,點)anda(possiblyempty)setE(G)of2-elementsubsetsofV(G)call

4、ededges(orlines,邊).V(G):vertexsetofG(只有一個G時常簡寫為V)E(G):edgesetofG(只有一個G時常簡寫為E)常見的edge表示法:{u,v}={v,u}=uv(orvu)當邊有方向性時稱G為directedgraph(digraph)Ch1-7ExampleAgraphG=(V,E),whereV={u,v,w,x,y,z}E={{u,v},{u,w},{w,x},{x,y},{x,z}}E={uv,uw,wx,xy,xz}G的diagram表示法:vuwxyzC

5、h1-8u,v:verticesofagraphGuandvareadjacentinGifuvE(G)(uisadjacenttov,visadjacenttou)e=uv(ejoinsuandv)(eisincidentwithu,eisincidentwithv)AdjacentandIncidentuveCh1-9Graphstypesundirectedgraph:(simple)graph:loop(),multiedge()multigraph:loop(),multiedge()P

6、seudograph:loop(),multiedge()loopmultiedges,paralleledgesCh1-10orderandsizeThenumberofverticesinagraphGiscalleditsorder(denotedby

7、V(G)

8、).Thenumberofedgesisitssize(denotedby

9、E(G)

10、).Proposition1:If

11、V(G)

12、=pand

13、E(G)

14、=q,thenAgraphoforderpandsizeqiscalleda(p,q)

15、graph.Ch1-11Applicationofgraphs一群人間兩兩互相認識或不認識(i.e.,沒有A認識B但B不認識A的情形)，在安排一張圓桌的晚餐座位時，是否存在一種排法能讓坐在一起的人都相互認識？eg.Tom,DickknowSue,Linda.HarryknowsDickandLinda.TomDickSueLindaHarryacquaintancegraph:(連線表示認識)(Ch8Hamiltoniangraph)Q:圖中是否有一個通過所有點的cycle?Ch1-12ADEBCeg.A

16、nimals:A,B,C,D,EAC不能與BD同區，E不能與其他動物同區Applicationofgraphs動物園要用圍牆劃分區域，避免同區的動物互相捕食，至少需分多少區？Q:將圖形的點著色(一色表示一區)，若相鄰兩點需塗不同色，最少需多少顏色才夠？連線表示不能同區Ans:3色3區(Ch10GraphColoring)Ch1-13HomeworkExercise1.1:1,2,3,4Ch1-