7.02 Networks and Graphs Flashcards
(37 cards)
What is a vertex or a node?
Points on a graph
What is an arc or an edge?
A line connecting vertices or nodes
What is a loop?
An arc with the same vertex at both ends
When does a pair of vertices have multiple arcs?
A pair of vertices has multiple arcs if there is more than one arc that connects them.
What is a degree or order?
The degree (or order) of a vertex is the number of arcs incident on it.
What do the rows represent on an adjacency matrix?
When you add up a row on an adjacency matrix it tells you the outdegree of a vertex
What do the columns represent in an adjacency matrix?
When the numbers are added up in a column of an adjacency matrix, it tells you the indegree of a vertex
What are two vertices called which are directly connected to each other?
Adjacent
What is a walk?
A walk is a set of arcs where the end vertex of one is the start vertex of the next.
In a walk, can arcs be repeated?
In a walk, any arc can be repeated and any vertex can be visited more than once.
What is a trail?
A trail is a set of arcs where the end vertex of one is the start vertex of the next. No arc is repeated.
Can arcs be repeated in a trail?
No arc can be repeated.
What is a path?
A path is a set of arcs where the end vertex of one is the start vertex of the next.
No arc can be repeated and no vertex can be revisited more than once.
In a path, can arcs and vertices be repeted or visisted more than once?
No arc can be repeated and no vertex can be revisited more than once.
What is a cycle?
A cycle is a closed path. Closed means that the final vertex is the same as the start vertex (this does not count as visiting the vertex more than once).
What is a route?
A route may be a walk, a trail or a path, or may be a closed walk, trail or path.
Can cycles have repeated arcs and can a vertex be visisted more than once?
A cycle has no repeated arcs and no vertex is visited more than once.
What is a connected graph?
A connected graph is one in which every vertex is joined, directly or indirectly, to each of the other vertices.
What is a simple graph?
A simple graph is a graph with no loops and no multiple arcs.
What is a simply connected graph?
A simply connected graph is a graph that is both simple and connected.
A connected graph is one in which every vertex is joined, directly or indirectly, to each of the other vertices. A simple graph is a graph with no loops and no multiple arcs
What is a complete graph?
A simply connected graph is complete if every possible pair of vertices is connected by an arc, so that it has the maximum possible number of arcs.
What is the equation for the number of arcs using the number of vertices (n) for a complete graph?
arcs = n(n-1) / 2
What is a tree?
A tree is a simple connected graph with no cycles.
What is the equation for the arcs of a tree?
Arcs = n-1
