Graphs Flashcards
What is a tree?
A connected graph with no cycles.
What is a planar graph?
One that can be drawn so no arcs cross
What is a simple graph?
Has no loops and at most one edge connecting any pair of vertices
What are the points on a graph called?
Vertices or nodes
What are the lines called on a graph?
Edges or arcs
What is a network?
A graph with weighted edges
What is a degree or order of valency?
The number of edges connected to a vertex.
What is an isomorphic graph?
An Isomorphic graph are graphs which show the same info but may be drawn differently.
What is a walk?
A sequence of edges where the end vertex of one edge is the start vertex of the next.
What is a trail?
A trail is a walk where none of the edges are repeated.
What is a path?
A path is a trail where none of the vertices are repeated
What is a cycle or circuit?
A closed path ie the end of the path joins back to the beginning.
What is the Handshake Lemma?
In any undirected graph, the sum of the degrees of the vertices is equal in o 2x the the no. of edges, as a consequence the no. of odd vertices must be even.
