Help shape GoConqr. What should we add next?

Flashcards

Graph Theory

artibv English 24 cards

Cards in this deck (24)

  1. 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.
  2. 2OrderThe order of a graph, denoted by |G| is the number of vertices.
  3. 3SizeThe size of a graph, denoted by e(G) is the number of edges.
  4. 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
  5. 5NeighbourhoodThe neighborhood of x, denoted by N(x), is the set of such y so that d(x)=|N(x)|
  6. 6Empty Graph on n verticesThat which has no edges at all. |G|=n, e(G)=0
  7. 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)
  8. 8SubgraphIf G=(V,E) is a graph, we say that H=(V',E') is a subgraph of G if V'⊂V and E'⊂E
  9. 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)
  10. 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)
  11. 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.
  12. 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
  13. 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
  14. 14ConnectedWe say that a graph is connected if there exists a path between any two vertices
  15. 15Mantel's TheoremIf G is a graph of order n and e(G)>(n^2)/4 then G contains K(3)
  16. 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).
  17. 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.
  18. 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)
  19. 19Hamiltonian CycleCycles which contain every vertex of G
  20. 20Dirac's TheoremIf |G|≥3 and d(X)≥|G|/2 for all x∈G then G contains a Hamiltonian cycle.
  21. 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
  22. 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.
  23. 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)
  24. 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

Feedback

What is it about?

What should we add next?