Network Definitions

OCR MEI D1 for all those who are with that stupid exam board XD

Nodes and Arcs

Nodes (Vertices)

Items

Arcs (Edges)

Connections/Relationships

1 of 6

Graph

• A set of nodes together with a set of edges
2 of 6

• An edge has a vertex or node at each end. If the vertex is the same one it is called a loop
• The degree/order of a vertex is how many lines there are coming off it
• A simple graph has no loops or double edges
3 of 6

Walks, Trails and Paths

• A walk is a sequence of edges in which the end of one is the start of another
• A trail is a walk in which no edge is repeated
• A path is a trail in which no vertex is repeated
4 of 6

Cycles and Hamilton Cycles

• A cycle is a closed path where the end node is the start node
• A Hamilton Cycle is a cycle that visits every node
5 of 6

More on Networks

• A graph is connected if there exists a path between every pair of nodes
• A tree is a simple connected graph with no cycles
• A diagram is a graph with direction
• A complete graph is a graph which has an edge between every pair of nodes
• An isomorphic graph is when two graphs can be redrawn to be the same
• A planar graph can be drawn without any edges crossing
• A bipartite graph is a graph where the nodes are split into 2 groups and the edges go from one group to the other
6 of 6