Decision 1 Unit 2 Flashcards
What are the lines called?
Arcs (or edges)
What are the dots/circles called?
Nodes (or vertices)
What is the order of a node?
The number of arc ends attached to the node
What is a simple graph?
A graph with no loops and no multiple arcs connecting the same nodes.
What is a trail?
A sequence of arcs where the end none of one arc is the start node of the next.
What is a path?
A trail where no node is passed more than once
What is a closed trail?
A trail that begins and ends at the same node
What is a cycle?
A closed trail where only the beginning and end nodes are the same. Apart from this no nodes can be used twice.
What is a connected graph?
A graph where there can be a trail found between any node to another
What is a Eulerian graph?
A graph where there can be a closed trail which uses every arc only once (but nodes can be used more than once).
Every node must have an even order.
What is a semi-Eulerian graph?
A graph with a trail (that isn’t closed) using every arc only once.
Only two nodes must have an odd order.
What is a complete graph?
A graph where each of the nodes is connected to every other node by only one arc. (eg. a triangle)
What are isomorphic graphs?
Two graphs where all of the nodes are connected to the same arcs, but they are just drawn in a different shape.
What is an expression for the number of arcs on Kn
1/2 n (n-1)
How many arcs are there on a connected bipartite graph Kr,s
rs
