Flashcards
Graph Theory
Cards in this deck (24)
- 1GraphFinite set of vertices, some of which are connected by a single edge. We don't allow multiple edges between two vertices, or an edge from a vertex to itself. It is defined by two pairs of data: a finite set V called the vertices of G and a set E of unordered pairs of elements of V called the edges of G.
- 2OrderThe order of a graph, denoted by |G| is the number of vertices.
- 3SizeThe size of a graph, denoted by e(G) is the number of edges.
- 4DegreeThe degree of a vertex x, denoted by d(X) is the number of y s.t x~y, that is the number of edges adjacent to x
- 5NeighbourhoodThe neighborhood of x, denoted by N(x), is the set of such y so that d(x)=|N(x)|
- 6Empty Graph on n verticesThat which has no edges at all. |G|=n, e(G)=0
- 7Complete graph on n verticesThe graph with n vertices and every possible edge, so that
e(G)=(n)
(2)
and x~y whenever x≠y. It is denoted by K(n) - 8SubgraphIf G=(V,E) is a graph, we say that H=(V',E') is a subgraph of G if V'⊂V and E'⊂E
- 9Induced SubgaphIf H=(V', E') is a subgraph of G=(V,E) and includes every possible edge (those present in G) between its vertices, that is if x, y ∈V' and {x,y}∈E(G) then {x,y}∈E(H)
- 10IsomorphismAn isomorphism between two graphs φ: G(1)→G(2) is a bijection between V(G(1)) and V(G(2)) s.t x~G(1)~y and φ(x)~G(2)~φ(y)
- 11BipartiteA graph is bipartite if we can partition the vertex set V(G) into two disjoint sets V(1) and V(2) s.t every edge of G goes between the two sets and there are no 'interior' edges- that is if x~y then x ∈V(1) and y∈V(2) or vice versa.
- 12PathA path of length l, denoted by P(l), is a graph with vertex set {0,...,l} and edge set E(P(l))={{i,i+1}:0≤i
- 13CycleA cycle of size l (and order l), denoted by C(l), is a path of length l-1 with an added edge between 0 and l-1
- 14ConnectedWe say that a graph is connected if there exists a path between any two vertices
- 15Mantel's TheoremIf G is a graph of order n and e(G)>(n^2)/4 then G contains K(3)
- 16MatchingsLet G be a bipartite graph with vertex classes V(1) and V(2). A matching from V(1) to V(2) is a set of independent edges (edges which do not touch each other) which cover every vertex in V(1).
- 17Necessary, not sufficient conditions for matchings1. There must be at least one vertex in V(2) for every vertex in V(1) since a matching gives an injective function from V(1) to V(2)
2. If |V(1)|=m, then the graph must have atleast m edges, one for each vertex of V(1) we need to match. - 18Hall's TheoremA bipartite graph G with vertex sets V(1) and V(2) has a matching from V(1) to V(2) iff |N(X)|≥|X| for all X⊂V(1)
- 19Hamiltonian CycleCycles which contain every vertex of G
- 20Dirac's TheoremIf |G|≥3 and d(X)≥|G|/2 for all x∈G then G contains a Hamiltonian cycle.
- 21r-partite graphFor any r≥1 an r-partite graph is one where we can partition V(G) into disjoint sets V(1),...,V(r) s.t if x,y∈V(i) then x~/~y
- 22Tr(n)Tr(n) is the complete r-partite graph with n vertices, where the sizes of the r vertex classes differ by at most 1 from each other.
- 23Turan's TheoremIf |G|=n and e(G)>tr(n) then G contains a K(r+1). Furthermore, if e(G)=tr(n) and G contains no K(r+1) then it is isomorphic to Tr(n)
- 24Ramsey NumberFor any graphs G and H, the Ramsey number R(G,H) is the smallest n s.t every colouring of the edges of K(n) red and blue will create either an all red copy of G or an all blue copy of H.
Information
- Description
- Flashcards on Graph Theory, created by artibv on 28/04/2015.
- Created by
- artibv
- Views
- 1
- Rating