Terminology (Leaving Cert Applied Maths): Revision Notes

Terminology

Graph theory is a fascinating area of mathematics that helps us understand networks and connections. Think of it like mapping friendships on social media or finding the best routes between cities. Let's explore the essential terminology you need to know.

Basic components of graphs

A graph is essentially a mathematical way of showing relationships between different objects. It consists of two main parts that work together to create these visual representations.

Vertices and nodes are the fundamental building blocks of any graph. These are simply points or dots that represent the objects we're studying. Whether you call them vertices or nodes doesn't matter - they're the same thing! Think of them as cities on a map or people in a social network.

Edges and arcs are the connections between vertices. These are the lines that join vertices together, showing that there's some kind of relationship between them. Like roads connecting cities or friendships linking people together.

This diagram shows how vertices (the Irish cities) are connected by edges, creating a network that represents relationships between these locations.

Understanding vertex degree

The degree of a vertex (also called valency or order) tells us how many connections that particular vertex has. It's simply the number of edges that meet at that vertex.

The concept is crucial because it helps us understand the importance or centrality of different vertices within a network.

Weighted graphs

Sometimes we need more than just knowing whether two vertices are connected - we need to know the strength or cost of that connection. This is where weights come in.

Weights are numerical values assigned to edges. These numbers could represent distances between cities, costs of transportation, or strength of relationships.

Weighted graphs are particularly useful in real-world applications like finding the shortest route for delivery trucks or determining the most cost-effective way to connect different locations.

Directed versus undirected graphs

Graphs can show different types of relationships, and this is where the concept of direction becomes important.

Undirected graphs have edges without arrows, meaning the relationship goes both ways.

Directed graphs (or digraphs) have edges with arrows showing the direction of the relationship.

Understanding subgraphs

A subgraph is like a smaller version of a larger graph, but with strict rules about what can be included.

Think of it like selecting a group of friends from your entire friendship network - you can only include the friendships that actually exist, not create new ones.

Simple graphs and loops

Not all graphs follow the same rules about connections, which leads us to important distinctions.

A simple graph follows two key rules: it has no loops (edges from a vertex to itself), and it has at most one edge between any pair of vertices. Most basic network diagrams you'll encounter are simple graphs.

A loop is a special type of edge that connects a vertex to itself. While they might seem odd, loops can represent important real-world situations, like a person having a relationship with themselves or a city having internal transportation systems.

Walks, paths, and cycles

Understanding how to move through a graph is essential for many applications.

A walk is a sequence of edges where you move from one vertex to another. The length of a walk is determined by the number of edges you traverse. You're allowed to visit the same vertex multiple times during a walk.

A path is a special type of walk where all vertices are different - you never visit the same vertex twice. Paths are like taking a journey where you never backtrack to a place you've already been.

A cycle is a closed path that starts and ends at the same vertex. Think of it like taking a circular route that brings you back to your starting point.

Connected graphs

The concept of connectivity tells us whether we can reach every part of a graph from any starting point.

A graph is connected if there's a path between every pair of vertices. This means you can travel from any vertex to any other vertex by following the edges. If this isn't possible, the graph is disconnected.

Adjacency and incidence

These terms describe the relationships between vertices and edges in precise mathematical language.

Two vertices are adjacent if they're directly connected by an edge. Think of adjacent vertices as immediate neighbours in the network.

Incidence describes the relationship between vertices and edges. When an edge connects two vertices, we say the vertices are incident with the edge, and the edge is incident with the vertices. It's simply a formal way of saying "this edge touches these vertices."

Trees and spanning trees

Trees are special types of graphs with unique properties that make them incredibly useful.

A tree is a connected graph with no cycles. Think of a family tree or the branching structure of an actual tree - there's always exactly one path between any two points, and there are no closed loops.

A spanning tree of a graph is a subgraph that includes all the original vertices and forms a tree. It's like finding the minimum number of edges needed to keep all vertices connected without creating any cycles.

A minimum spanning tree is the spanning tree with the smallest total weight when working with weighted graphs. This concept is crucial in network design, helping find the most cost-effective way to connect all points in a network.

The hand-shaking lemma

This important theorem provides a fundamental relationship in graph theory.

The Hand-shaking Lemma states that the sum of all vertex degrees in a graph equals twice the number of edges. This happens because each edge contributes to the degree of exactly two vertices.

This lemma is incredibly useful for checking your work and understanding the structure of graphs. It's called the "hand-shaking lemma" because if you imagine each edge as a handshake between two people, each handshake involves exactly two hands.