Network types Notes

1. Graphs in graph theory are a powerful way to model connections in real life, such as rail routes, social interactions, or metro maps.
2. In this topic you will learn the main network types used in extended mathematics and how to recognize what each type can (and cannot) represent.

Graphs Model Connections Using Vertices And Edges

1. A graph (in graph theory) is made of vertices (points) and edges (connections between points).
2. This is a different meaning from the word "graph" used for plots on coordinate axes, so you must be careful with terminology.
3. Vertices are also commonly called nodes, and edges are also called arcs.

Order (Degree) Describes How Connected A Vertex Is

1. The order of a vertex (also called its degree) is the number of edges connected to it.
2. This is one of the simplest but most useful measurements in network problems:
   1. a high-order vertex may represent a major hub station in a metro system,
   2. a low-order vertex may represent an isolated location with few direct links.

Undirected Graphs Model Two-Way Relationships

1. In an undirected graph, an edge means the relationship works both ways.
2. This is appropriate when travel or connection is symmetric, for example:
   1. two people who can communicate (they share at least one common language),
   2. two stations joined by track that trains run in both directions,
   3. two computers connected by a cable where data can flow either way.

Connected And Disconnected Graphs Describe Reachability

1. A key property of an undirected graph is whether it is connected.
2. If a graph is not connected, it is disconnected, meaning it has at least two separate parts (components) with no path between them.

Complete Graphs Represent "Everyone Connects To Everyone"

Some networks are maximally connected.

Complete graphs are useful as idealized models (for example, if every city has a direct flight to every other city), but they become unrealistic quickly as the number of vertices grows.

Directed Graphs Model One-Way Connections

1. Sometimes the relationship is not symmetric.
2. Then we use a directed graph.

Directed graphs are appropriate for:

1. one-way streets,
2. online "following" (A follows B does not imply B follows A),
3. processes with a fixed direction (task A must happen before task B).

In-Degree And Out-Degree Extend The Idea Of Order

1. For directed graphs, we often separate "order" into:
   1. out-degree: number of arrows leaving a vertex,
   2. in-degree: number of arrows entering a vertex.
2. This helps answer questions like: which page has the most links pointing to it, or which station has the most one-way exits?

Weighted Graphs Are Networks Used For Optimization

1. Knowing that two places are connected is useful, but it is often not enough to make decisions.
2. If you want to choose a best route, you need information about the connections.
3. A network is a weighted graph, meaning each edge has a value (a weight) attached.

Why Weight Matters: Two Routes Can Use The Same Number Of Edges But Differ Greatly

1. In an unweighted graph, two paths might look equally good if they use the same number of edges.
2. In reality, one route may be much quicker or cheaper.
3. For example, if you can travel from Derby to Liverpool with one change via Birmingham or via Crewe, the unweighted graph only tells you both are possible.
4. A network, with edge weights for time, distance, or cost, would let you decide which route is better.

Bipartite Graphs Model Relationships Between Two Different Sets

Some graphs naturally split into two groups, where edges only go between groups, not within a group.

1. A classic example is a "people and languages" graph:
   1. one set of vertices represents people,
   2. the other set represents languages,
   3. an edge means "this person speaks this language".
2. In such a graph, the order of a person-vertex represents how many languages they speak, and the order of a language-vertex represents how many people speak it.

Projecting A Bipartite Graph Creates A "Shared Feature" Network

1. Sometimes you want a graph that shows connections only among people.
2. From a people-and-languages bipartite graph, you can make a new graph:
   1. vertices are people,
   2. connect two people if they share at least one language.
3. This new graph is often more useful for answering questions about who can communicate with whom, but it also loses information (you no longer see which language creates the connection).