Graphs and Networks Flashcards
What is a complete graph?
A graph where each node is connected by one arc to each other node
What is a node?
The blobs/dots
What is an arc?
The lines
What is a vertex?
The blobs/dots
What is an edge?
The lines
What are two terms for the lines in a graph?
Arcs and Edges
What are two terms for the blobs/dots in a graph?
Nodes and Vertices
What is a trail?
A walk where no edge appears more than once
What is a path?
A trail in which no vertices are visited more than once
What is a cycle?
A closed path that finishes at the same vertex that it started at
What classifies as a connected graph?
When all vertices are connected
What is a simple graph?
A graph with no loops, and no more than one edge connecting a pair of vertices
What is the degree/order of a vertex?
The number of edges connected to it
What is a digraph?
A graph with edges that have a specified direction (through arrows). Orders have no meaning in these graphs.
What is a tree?
A connected graph with no cycles
What is a network?
A graph with weights (numbers) associated with the edges
Define a Eulerian graph
A connected graph with only even orders.
Define a semi-Eulerian graph
A connected graph with only two odd orders
Explain why an Eulerian graph can only have nodes of even order
In a closed trail containing every arc once, each time a node occurs it has an arc going in and an arc going out. Each node is therefore at the end of an even number of arcs, and therefore has an even order.
What is Kn used for and what does it show?
It is the notation for a complete graph with n nodes
What is a bipartite graph?
Two sets of nodes, with arcs only connecting one to the other and not connecting nodes within one set
Analyse Kr,s in terms of being Eulerian and semi-Eulerian
If r and s are both even, it will be Eulerian. If r and s = 1 the graph is semi-Eulerian. If r or s = 2 and the other is an odd number, the graph is semi Eulerian.
What does Kr,s show.
A bipartite graph, with r showing the number of nodes in one set and s showing the other.
What is the total number of arcs in a Kr,s graph?
r x s
What is the order of a Kn graph?
n-1
