Simple Graphs

本节主要学习简单图形。本文介绍了多种类型的Simple Graphs,并举例说明。同时本文还简要说明同构图、二部图和一些特别的图的组成。
展开查看详情

1.Simple Graphs aka “Undirected Graphs” 3/19/12 1

2.Types of Graphs Directed Graph Multi-Graph Simple Graph this week before spring break 3/19/12 2

3.A simple graph: Definition: A simple graph G consists of a nonempty set, V , of vertices , and a set, E , of edges such that each edge has two distinct endpoints in V Write G = (V,E) 3/19/12 3

4.vertices, V undirected edges, E A Simple Graph ::= { , } edge “adjacent ” 3/19/12 4

5.A simple graph G: b d a e f c V ={ a,b,c,d,e,f } E ={{ a,d },{ a,e },{ b,c },{ b,e }, { b,f },{ c,f },{ d,f },{ e,f }} picture of G 3/19/12 5

6.degree of a vertex is # of incident edges Vertex degree deg( ) = 2 3/19/12 6

7.Vertex degree deg( ) = 4 degree of a vertex is # of incident edges 3/19/12 7

8.Possible Graph? orphaned edge Is there a graph with vertex degrees 2,2,1? NO! 2 2 1 Im possible Graph ? 3/19/12 8

9.sum of degrees is twice # edges Handshaking Lemma Proof : Each edge contributes 2 to the sum on the right 3/19/12 9

10.Handshaking Lemma sum of degrees is twice # edges 2+2+1 = odd, so impossible 3/19/12 10

11.Sex in America: Men more Promiscuous? Study claims: Men average many more partners than women. Graph theory shows this is nonsense 3/19/12 11 http://drjengunter.wordpress.com/2011/12 /03/how-many-sex-partners-do-people-really-have/

12.M partners F Sex Partner Graph 3/19/12 12

13.Counting pairs of partners divide by both sides by |M| 3/19/12 13

14.Averages differ solely by ratio of females to males . No big difference Nothing to do with promiscuity Average number of partners 1.035 3/19/12 14

15.Some Special Graphs Complete graph K n : A graph with n vertices including all possible edges K 5 : 3/19/12 15

16.Bipartite Graph Graph in which vertices fall into two disjoint subsets and all edges have one endpoint in each 3/19/12 16

17.Isomorphic Graphs Graphs (V,E) and (V’,E’) such that there is a bijection f : V→V’ that preserves edges: { v,w}∈E iff { f(v),f( w )}∈ E ’ Any two complete graphs of the same size are isomorphic 3/19/12 17 1 2 b d a e f c 3 4 5 6 a 2 b 4 c 6 d 3 e 1 f 5

18.Finis 3/19/12 18