Graphs Flashcards
What are the dots called?
Vertices or Nodes
What are the lines called?
Edges or Arcs
What is a simple graph
No loops and there is no more than one edge connecting any pair of vertices
What is a complete graph?
A graph in which every vertex is connected to every other vertex
What is a walk?
A sequence of edges in which the end of one edge (except the last) is the beginning of the next
What is a trail?
A walk in which no edge is repeated
What is a path?
A trail such that no vertex is visited more than once (except that the first vertex may also be the last)
What is a cycle?
A closed path Eg. The end of the last edge is the start vertex of the next
What is a hamiltonian cycle?
A cycle which visits every vertex once and only once
What is a traversable graph?
One that can be drawn without taking a pencil from the paper and without retracing the same edge
What is a Eulerian graph?
A graph which can be traversed by starting and finishing at the same node, without retracing an edge
What is a semi-Eulerian graph?
A graph where you start at a node, traverse each edge exactly once and end up somewhere different to the starting point
What is a bipartite graph?
A graph consisting of two sets of vertices. The edges only join vertices in X to vertices in Y.
What is a connected graph?
A graph in which every vertex is joined directly or indirectly to every other vertex
What is a tree?
A connected graph with no cycles
What is a digraph?
A graph in which at least one edge has a direction associated with it
What is an incidence matrix?
A way of representing the number of edges between nodes in a matrix
What is an isomorphic graph?
Two graphs that can be stretched, twisted or otherwise distorted into each other
What is a planar graph?
A graph which can be drawn without any edges crossing
What is a subgraph?
A subset of the vertices together with a subset of edges in a graph
