Graphs and Networks Flashcards
What is a graph
A diagram involving a set of points and interconnecting lines
What is a vertex
A point on a graph
What is an edge/arc
A line connecting two nodes/vertices
What is an isomorphic graph
two or more graphs that show the same set of vertices and connections
What is a connected graph
A graph where you can travel from any vertex to any other vertex via edges
What is a multiple edge
two or more edges that connect the same pair of vertices
What is a loop
a vertex connected to itself
What is a simple graph
A graph with no loops or multiple edges
What is a subgraph
A graph formed using only some of the vertices and edges of the original graph
What is a sub-division
if you add an extra vertex along the edge of a graph
what is a complete graph and its notation
a simple graph that has an edge connected it to all possible vertex pairs. Notation Kn where n = number of vertices.
what is a planar graph
A graph where none of the edges cross over eachother
what is the degree of a vertex
the number of edges coming out of a vertex
what is the formula linking the total degrees and total edges
total number of degrees = 2 x total edges
What is Euler’s formula
v + f - e = 2
What is an adjacency matrix
a table showing the vertices and number of connections between them
what is a compliment graph and its notation
a graph formed by drawing all the edges that don’t exist in the original graph and removing those that do (G’)
What is a trail
a continuous journey around a graph with no repeated edges
what is a closed trail
a trail that returns to its start vertex
what is a path
a continuous journey around a graph with no repeated edges or vertices
what is a cycle
a path that returns to its start vertex
what is a tree
a connected graph with no cycles
What is a hamiltonian cycle
a cycle that visits every vertex once
what is an Eulerian Graph and how can you tell
A trail that starts and finishes in the same place, all it’s vertices have an even degree
