Chapter 2 Graphs and Networks Flashcards
What is a graph?
A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs)
What is a graph where each edge has a numbers associated with it called?
Weighted graph or a Network
What is a weighted graph/network?
A graph withy numbers associated with each edge
In a weighted graph, what are the numbers usually called?
Its weight
What is a vertex?
A point in the graph
What are vertices sometimes called?
Nodes
What is an edge?
A line segment joining vertices
What is the other word for edge?
Arc
What do you need to be careful about with networks?
They aren’t usually drawn to scale
As a result the shortest path may not be the obvious path
That is the list of vertices called?
Vertex set
What is the list of edges called?
The edge set
What is the vertex set?
The list of vertices
What is the edge set?
The list of edges
What is a subgraph?
A subgraph is part of the original graph
When is a vertex and an edge incident?
If they are connected
What is the degree of a vertex?
The number of edges incident to a particular vertex
What are the other ways to say degree of a vertex?
Valency of a vertex
Order of a vertex
What does even degree mean?
The vertex has an even number of incident edges
The degree of vertex will be an even number
What deos odd degree mean?
The vertex has an odd number of incident edges
The degree of vertex will be an odd number
What phrase can be used to say: The vertex has an even number of incident edges?
Even degree
What phrase can be used to say: The vertex has an odd number of incident edges?
Odd degree
What is a walk?
A walk is a route through a graph along edges from 1 vertex to the next
What is a path?
A path is a walk in which no vertex is visited more than once
What is a trail?
A trail is a walk in which no edge is visited more than once