Graphs And Networks Flashcards
What does a graph consist of?
Vertices and nodes
What are nodes connected to?
Arcs
What is a graph named when it has a number associated with each edge?
A weighted graph or network
What is a subgraph?
Part of an original graph.
What is the degree of a vertex?
Number of arcs incident to it
What is another word for the degree of a vertex?
Valency or order
What is a walk?
A route through a graph along edges from one vertex to another
What is a path?
A walk in which no node is visited more than once.
What is a trail?
A walk in which no arc is visited more than once?
What is a cycle?
A walk in which the end node is the same as the start node
What is a Hamilton cycle?
A cycle which includes every node
What makes two nodes connected?
When an arc joins them
What makes a graph connected?
If all vertices are connected
What is a loop?
An arc that starts and finishes at the same node
What is a simple graph?
Where there are no loops and only one arc connects a pair of nodes
What is a graph called if it has directions associated with the arcs?
A digraph
What is Euler’s handshaking lemma?
That any undirected graph has a some of degrees equal to 2x the edges. This means the number of odd nodes must be even.
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A subgraph which includes all the vertices of the original graph.
What is a complete graph?
A graph in which all nodes connect to all other nodes once
What is an isomorphic graph?
Graphs which show the same information but are formed differently.
What does each unit in an adjacency matrix represent?
The number of arcs joining a pair of nodes
What does each unit represent in a distance matrix?
The weight of each arc
