Graph And Network Theory Flashcards
What is a graph?
A graph is a collection of nodes connected by edges.
What are the points and lines on a graph called?
The lines are called arcs or edges and the point are called nodes or vertices.
What is a network?
A network is a graph that has numbers assigned to each edge (a weighted graph).
What is a digraph?
A diagraph is a graph that has arrows on the edges, showing direction.
What is a subgraph?
Any graph (B) is a subgraph of any graph (A), if all the nodes and edges in B are nodes and edges in A.
What is a loop?
A loop is an edge that starts and finishes at the same node.
What are isomorphic graphs?
Isomorphic graphs are where 2 graphs are identical, same degree, same number of nodes and edges.
What is the degree of a node or graph?
The degree is the number of edges incident to a/each node.
What is a simple graph?
A graph is simple if it doesn’t have any loops or multiple edges between 2 nodes.
What is a walk?
A walk is a succession of edges where the end of one is the start of the next.
What is a path?
A path is a walk where all the nodes are different.
What is a closed walk?
A closed walk is a walk that starts and ends at the same node.
What is a cycle?
A cycle is a path that starts and ends at the same node.
What is a connected and disconnected graph?
If there is a path between any pair of nodes, the graph is connected. A graph is said to be disconnected if there is no path between two nodes causing the graph to be broken into components.
