Network Definitions

Nodes (Vertices)

Items

Arcs (Edges)

Connections/Relationships

• A set of nodes together with a set of edges

• 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

• 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

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

• 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