Decision Chapter 2: Graphs and Networks

29 flashcards · Mathematics · by TheoTyson

1. What is a graph?

   Consists of points which are connected by lines.

2. What are vertices / nodes?

   Points on a graph.

3. What are edges / arcs?

   Lines joining vertices on a graph.

4. What is the weight?

   Number associated with each edge.

5. What is a weighted graph?

   When each edge has a number associated with it.

6. What is a vertex set?

   List of vertices in a graph.

7. What is an edge set?

   List of edges in a graph.

8. What is a subgraph?

   A part of the original graph.

9. What is the order / degree / valency?

   The number of edges that are incident to a vertex.

10. What is a walk?

    A route through a graph along edges from one vertex to the next.

11. What is a path?

    A walk in which no vertex is visited more than once.

12. What is a trail?

    A walk in which no edge is visited more than once.

13. What is a cycle?

    A walk in which the start and end vertex are the same, and no other vertex is visited more than once.

14. What is a hamiltonian cycle?

    A cycle that include every vertex.

15. What are connected vertices?

    Two vertices with a path between them.

16. What is a connected graph?

    If all of the vertices are connected.

17. What is a loop?

    An edge that starts and finishes at the same vertex.

18. What is a simple graph?

    A graph with no loops, and there is at most one edge connecting any pair of vertices.

19. What are directed edges?

    If the edges of a graph have a direction associated.

20. What is a directed graph?

    When the edges of the graph have directions associated with them.

21. What is Euler's handshaking lemma?

    The sum of the degrees of the vertices is equal to 2 x the number of edges. The number of odd vertices must be even.

22. What is a tree?

    A connected graph with no cycles.

23. What is a spanning tree?

    A subgraph that includes all of the original vertices and is also a tree.

24. What is a complete graph?

    A graph in which every vertex is directly connected by a single edge to each other vertex.

25. What is the notation for a complete graph?

    KnK_nKn​ (n vertices)

26. What are isomorphic graphs?

    Graphs that show the same information but can be drawn differently.

27. What are the criteria for isomorphic graphs?

    Same number of vertices. Vertices with the same number of degrees. The vertices must be connected in the same ways.

28. What is an adjacency matrix?

    Each entry in the matrix describes the number of edges joining the corresponding vertices.

29. What is a distance matrix?

    Each entry in the matrix represents the weight of each edge.