GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

Graph Theory Definitions Weeks 1-5

florencetrodd Graph Theory 3033 Degree English 74 cards

Cards in this deck (74)

  1. 1EdgeAn edge is an unordered pair of vertices
    i.e. {v, w} € E
  2. 2Adjacent (for vertices and edges)Two vertices v, w € V are adjacent if there is an edge between v and w.
    Two edges e, f € E are adjacent if they have a common endpoint
  3. 3Neighbours NeighbourhoodNeighbours of x are the vertices adjacent to x.
    The set of adjacent vertices of x is called the neighbourhood of x, N(x).
  4. 4A vertex is incident to an edge ifthe vertex is an endpoint of the edge
  5. 5The complement of GThe complete graph K (v(G)) minus G.
  6. 6Coprime GraphVertices are joined by an edge if the gcd of the edges is 1
  7. 7isomorphism of G onto Hone-to-one map @ from V(G) onto V(H) where a and b are adjacent vertices in G if a@ and b@ are adjacent vertices in H
  8. 8If G=< H, the complement of G in H isH-G
  9. 9Degree d(x)the number of edges that have x as an endpoint
  10. 10delta (x) DELTA (x)delta (x) is the minimum degree in the graph
    DELTA (X) is the maximum degree in the graph
  11. 11Let G be a finite simple graphA graph with:
    - at most one edge between any pair of distinct vertices (no loops).
    -the edge is NOT directed.
    - finite vertex set
    -finite edge set
  12. 12The Hand-Shaking Lemmathe sum of d(x) = 2|E(G)|
  13. 13WalkLGBAFSG
    a walk is a finite sequence of vertices and edges:
    x0, a1, x1, a2, ..., an, xn
  14. 14simple walkonly distinct edges
  15. 15length of a walknumber of edges
  16. 16Patha walk where all the vertices are distinct
  17. 17closed walkx0 = xn
    i.e. the first vertex is the same as the last vertex
  18. 18A Cycle of length nA closed walk of length n, where the vertices x0, ..., xn-1 are distinct
  19. 19Theorem 2.1 If there is a walk between vertices y and z, y/=z, thenthere is a path in G with first vertex y and last vertex z
  20. 20two vertices are connected when...there is a walk joining them
  21. 21two vertices are connected iff...they lie in the same component of G
  22. 22G is a connected graph iffall pairs of its vertices are connected
    i.e. if there is a walk between any two distinct vertices
  23. 23If vertices y,z € V are connected, their distance D(x,y) is...?the length of the shortest path joining them
  24. 24What are the three properties of D(x,y) ?1) D(x,y) >= 0 with D(x,y)=0 iff x=y
    2) D(x,y) = D(y,x) ... symmetry
    3) D(x,z) =< D(x,y) + D(y,z) ... triangle inequality
  25. 25eccentricitythe largest value of D(x,y) where y ranges through all the vertices
  26. 26diameterThe maximum value of e(x) for all vertices of G
  27. 27radiusthe smallest value of e(x)
  28. 28Conjecture involving radius and diameterR(G)=< D(G) =< 2R(G)
  29. 29CentreThe centre of G, C(G), is the set of all vertices x that have eccentricity e(x) = R
  30. 30The centre is never ... ?empty. All vertices have e(x).
  31. 31H is a subgraph of G ifV(H) is a subgroup of V(G)
    E(H) is a subgroup of E(G)
  32. 32H is a proper subgraph ifH /= G
    i.e.
    H
  33. 33induced subgraphH is the induced subgraph of G if:
    H is a subgroup of vertices of G together with the edges that join the vertices of H together.
  34. 34If H is the induced subgraph of G on V(G), thenH=G
  35. 35girththe length of the shortest cycle in G
  36. 36circumferencethe length of the longest cycle in G
  37. 37True or false? circumference (G) =< |V(G)|True
  38. 38In a cycle Cn, what does |V(Cn)| equal?|E(Cn)|
  39. 39Eulerian Grapha graph G that admits a closed eulerian walk
  40. 40Eulerian Walksimple closed walk containing every edge
  41. 41semi-eulerian graphA graph that has a non-closed eulerian walk
  42. 42Theorem 2.6 LGBAFSCG. G is eulerian iff every ?? has ?? degree G is semieulerian iff there exists exactly ?? ?? of ?? degreeG is eulerian iff every vertex has even degree
    G is semieulerian iff there exists exactly two vertices of odd degree
  43. 43Hamiltonian GraphLGBAFSCG
    G is hamiltonian if G admits a cycle containing all the vertices
  44. 44Semihamiltonian GraphG is semihamiltonian if G admits a path containing all the vertices
  45. 45Two examples of hamiltonian graphs(n =<3)
    Cn
    Kn
  46. 46Ore's TheoremLGBAFSCG with |V(G)| >= 3
    Suppose that d(x) + d(y) >= |V(G)| for all pairs x,y of non-adjacent vertices
    Then G is Hamiltonian
  47. 47Dirac's CorollaryLGBAFSCG with |V(G)| >= 3
    If d(x) >= V/2 for all x,
    then G is Hamiltonian
  48. 48G is bipartitie iff G contains no ??LGBAFSG.
    G is bipartite iff G contains no cycles of odd length
  49. 49G is bipartite ifV(G) = A U B
    A n B cannot be empty
    A, B cannot be empty
    E(G) join all vertices in A to all vertices in B
  50. 50Examples of bipartite graphscomplete bipartite graphs K m,n
    Cycles of even length
  51. 51When is the bipartite graph Hamiltonian?m=n >= 2
  52. 52When is the bipartite graph never hamiltonian?if m doesn't equal n
  53. 53Eulerian walkcovers all edges exactly once
    repeated vertices are allowed
  54. 54hamiltonian cyclecovers all vertices exactly once,
    repeated edges are allowed
  55. 55The complement of G on V verticesThe complete graph on V vertices minus G
  56. 56cutpointx € V(G) is a cutpoint if G-x isn't connected
  57. 57bridge cutedgean edge xy € E(G) such that G-xy is not connected
  58. 58Lemma 3.1 an edge xy € E(G) is a bridge iffxy is not contained in any cycle in G
  59. 59Lemma 3.2 how many components does G-xy have if xy € E(G) is a bridge?two
  60. 60If the degree of all x € V(G) is even, is there a bridge in G?No
  61. 61If there is an xy bridge in G, what effect does this have on the degree in G?d(x) is even for all the vertices
  62. 62connectivityThe connectivity of G, K(G), is the minimum value of n such that the removal of some set of n vertices disconnects G or results in a single vertex.
  63. 63What does K(G)=0 mean?G is disconnected from the start
  64. 64What does K(G) = 1 mean?G has a cutpoint
  65. 65K(G) >= KG is k connected
  66. 66edge connectivity k'(G)K'(G) is the minimum value of m such that the removal of some set of m edges disconnects G
  67. 67K(G) =< K'(G) =< delta(G)K(G) =< K'(G) =< delta(G)
  68. 68general walkno loops
  69. 69G is nonseperable ifG is nontrivial, connected and has no cutpoints
  70. 70A block in Gmaximal non-seperable subgraph
  71. 71A proper n-colouring of V(G)%:V(G) -> {1, .., n} so that if x,y€V(G) are adjacent, %(x) /= %(y)
  72. 72chromatic number X(G)smallest integer n such that G has an n-colouring
  73. 73Colourings (general)partitions of the vertex or edge set of a graph into subsets so that no two elements of the same subset are adjacent
  74. 74Are the following eulerian/ semieulerian? N3 N4 N5 N6 N7N3: eulerian
    N4: semieulerian
    N5: semieulerian
    N6: neither
    N7: semieulerian

Information

Description
Degree Graph Theory 3033 Flashcards on Graph Theory Definitions Weeks 1-5, created by florencetrodd on 26/12/2014.
Created by
florencetrodd
Views
36
Rating

Feedback

What is it about?

What do you think of the new look?

How do you like it?