Graph (discrete mathematics)

Dots can be joined by lines.

These dots are called vertices. The lines are called edges. Edges show how things connect.

Some lines go one way. These are called directed edges. They look like small arrows.

They show a path from one dot to another.

Other lines do not have arrows. These are undirected edges. They show a link between two dots.

This is like two people shaking hands.

Some dots have no lines. These are called isolated dots. Other dots can have many lines. They can even have a line that loops back to itself.

Graphs help us see how things work together.

Imagine you are at a party. You want to see who knows whom. You could draw a dot for every person. Then, you draw a line between people who shake hands.

In math, these dots are called vertices. The lines are called edges. This whole picture is called a graph.

Some edges are undirected. This means the link goes both ways. A handshake is a good example. Other edges are directed. These look like arrows.

They show a one-way path. For example, one person might owe money to another.

Graphs can be very special. A complete graph has edges between every single pair of dots.

A weighted graph gives each edge a number. This number might show how long a path is. Some graphs are mixed. They use both arrows and plain lines.

J. J. Sylvester first used the word "graph" in 1878. He saw how math could show chemical shapes. Today, graphs help us study many things.

Imagine you want to map out how things connect. You might draw dots to represent objects and lines to show their relationships. In mathematics, this special structure is called a graph.

The dots are known as vertices, or sometimes nodes. The lines connecting them are called edges, links, or lines. A graph can tell a story about how many items are in a group. The number of vertices is called the order of the graph. The number of edges is called the size of the graph.

Graphs work in different ways depending on the connections. Some graphs are undirected, meaning the relationship goes both ways. A handshake is a good example because both people participate at once. Other graphs are directed, which use arrows to show a specific direction.

In a directed graph, an edge might go from person A to person B. This is useful if person A owes money to person B. You might also see a mixed graph. This uses both regular lines and arrows in the same picture.

Mathematicians have studied these patterns for a long time. The word "graph" was first used in this way by J. J. Sylvester. He used the term in 1878.

Sylvester saw a link between math and the way chemicals are shaped. He thought of these diagrams as a way to show chemical structures. His work helped connect algebra to the physical world. This helped start the study of graph theory.

There are many specific types of graphs to explore. A complete graph is one where every single dot connects to every other dot.

A regular graph is one where every vertex has the exact same number of neighbors. Some graphs are also weighted.

In a weighted graph, each edge is given a number. This number might represent a cost or a distance. You can also have a path graph, which looks like a simple line of dots. Some graphs are even called trees if they follow certain rules.

Graphs help us understand the world around us. They are used to find the shortest path between two places. They can show how many people are connected in a large network. You can use them to study how computers share information. Even simple shapes like a cycle graph show us patterns.

By using vertices and edges, math turns messy connections into clear pictures. This makes hard problems much easier to solve.

In discrete mathematics, a graph is a formal structure used to model relationships between objects. It consists of a set of objects called vertices, which are also known as nodes or points. The relationships between these objects are represented by edges, which are often called links or lines.

By using these abstractions, mathematicians can study the patterns of connectivity without needing to know the specific nature of the objects themselves. This makes graph theory a powerful tool for analyzing everything from social networks to chemical structures.

To understand how a graph functions, we must look at its fundamental properties. The order of a graph refers to the total number of vertices in the set. The size of a graph refers to the total number of edges.

We also measure the degree, or valency, of a vertex, which is the number of edges connected to it. If an edge connects a vertex to itself, it is called a loop and counts twice toward the degree. When two vertices are connected by an edge, they are said to be adjacent. If a vertex has no edges connected to it, it is called an isolated vertex.

Graphs are categorized by how their edges behave. An undirected graph uses simple lines where the relationship is mutual, such as a handshake between two people.

In contrast, a directed graph, or digraph, uses edges with specific orientations, often drawn as arrows. In these cases, an edge has a tail and a head, indicating a one-way relationship like owing money.

Some systems require both types of connections, which are known as mixed graphs.

Furthermore, a multigraph allows multiple edges to exist between the same two vertices, while a simple graph does not.

The history of the term "graph" in this mathematical sense dates back to 1878. It was first used by the mathematician J. J. Sylvester. Sylvester noticed a direct relationship between mathematical invariants and chemical structures.

He drew connections between algebra and the way atoms are arranged in molecules, which he called chemico-graphical images. This insight helped bridge the gap between abstract mathematics and the physical science of chemistry. His work provided an early foundation for what we now call graph theory.

Mathematical graphs can be assigned specific values to add more detail. A weighted graph, or a network, assigns a numerical value, called a weight, to each edge.

These weights can represent many different real-world measurements, such as the distance between cities, the cost of a flight, or the capacity of a pipe. Using these numbers allows mathematicians to solve complex problems, such as finding the shortest path through a network. This is a central concept in many computational algorithms used today.

There are many specialized types of graphs that mathematicians study. A complete graph is a structure where every single vertex is joined to every other vertex by an edge.

A regular graph is one where every vertex has the exact same degree, meaning every point has the same number of neighbors. We also study bipartite graphs, where vertices are split into two groups that do not connect within themselves. Some graphs are even described as planar if they can be drawn on a flat surface without any edges crossing each other.

Connectivity is another vital concept in graph theory. In an undirected graph, a graph is considered connected if a path exists between every pair of vertices.

In directed graphs, the rules are more complex. A graph is strongly connected if there is a directed path from every vertex to every other vertex. If the connections only work when you ignore the direction of the arrows, the graph is called weakly connected. These distinctions help scientists understand how information or energy flows through a system. By studying these various structures, we gain a deeper understanding of the interconnected world around us.