Graphs Flashcards
What is a graph?
Abstract data type that is used to represent the non linear relationships between objects
Name what a graph consists of :
Nodes (vertices)
Edges(arcs)
What do you call it when two nodes are connected by an edge?
Neighbours
What is a degree of a node?
The number of other nodes that it is connected to
What is a loop?
An edge that connects a node to itself
What is a path?
Sequence of paths connected by edges
What is a cycle
Closed path. A path that starts and ends on the same node.
Give 2 examples of where graphs are used to represent a lot of different relationships.
- Social networking, where each node represents individual people. An edge could represent that two people are acquaintances.
- The internet: nodes could represent routers and the edge could represent that that the routers are connected.
What is the advantage of an undirected graph?
Allows you to move in either direction between nodes.
WHAT happens in directed graphs ?
Directed graphs have a direction , this m,earns you have to move in a specific direction. In these diagrams arrows are used instead of lines
In what direction are bidirectional arrows used ?
Double headed arrows.
What happens when a graph has values associated with edges ?
Weighted / labelled graph .
Why might you want to use weights to record information relating to the edges ?
For eg|: weights are used to give the distance and you can then be able to tell the shortest path between nodes.
