Graphs key words

Card Set Information

Graphs key words
2012-11-20 13:20:55
Further Maths

MEI FP1: Chapter 2
Show Answers:

  1. Graph
    A set of nodes together with a set of edges.
  2. Edge
    Has a node at each end.
  3. Loop
    Edge with the same node at each end.
  4. Degree (or order) of a node
    Number of edges incident (attached) to it.
  5. Simple graph
    Graoh with no loops, no more than one edge connecting any pair of nodes.
  6. Walk
    Sequence of edges where the end of one edge is the beginning of the next.
  7. Trail
    Walk in which no edge is repeated.
  8. Path
    Trail in which no node is repeated.
  9. Cycle
    Closed path (end of last edge is start of first edge).
  10. Hamiltonian cycle
    Cycle which visits every node.
  11. Connected graph
    Paths exist between every pair of nodes (each node has a degree of at least one).
  12. Tree
    Simple connected graph with no cycles.
  13. Digraph (directed graph)
    Graph where at least one edge has a direction to it.
  14. Complete graph
    Simple graph, every pair of nodes is connected by an edge.
  15. Incidence matrix
    Matrix that represents a graph.
  16. Isomorphic graphs
    Two graphs that can be distorted into each other (have the same connections).
  17. Planar graph
    Graph where no edges cross.
  18. Biparitie graph
    Graph with two sets of nodes, each node connected to another node in the opposite set