خصائص المخططات وتكلفة الوصلات

TL;DR

You'll learn about undirected graphs where connections don't have a specific direction. In these graphs, the connection between points X and Y is the same as Y and X, and their cost is also identical. This differs from directed graphs where cost can vary depending on the direction.

1. The Mental Model

Imagine a road connecting two cities. If you can drive from City A to City B, you can also drive from City B to City A, and the cost (maybe gas or tolls) is the same for either journey. This is generally how undirected graphs work.

2. The Core Material

In شبكات تينن (network design), we often work with different types of graphs. Your source material introduces us to undirected graphs (مخططات غير موجهة).

ما هي المخططات غير الموجهة؟

An undirected graph is a type of graph where the connections (called edges, or حواف) between two points (called vertices or nodes) do not have a specific direction.

This means:
* If there's an edge from point x to point y (represented as (x,y)), it's considered the exact same edge as the one from point y to point x ((y,x)). They are interchangeable.
* Similarly, the cost (تكلفة) associated with this edge, c(x,y), is identical to the cost c(y,x). The cost is the same regardless of which direction you traverse the edge.

This is a key distinction from directed graphs (مخططات موجهة). In a directed graph, an edge from x to y is distinct from an edge from y to x. Consequently, the cost c(x,y) might be completely different from c(y,x). Think of a one-way street or a flight path where flying one way costs more than the reverse.

Here's a simple way to visualize this difference:

graph TD
    A["مخططات"] --> B["غير موجهة"];
    A --> C["موجهة"];
    B --> D["الحافة (x,y) هي (y,x)"];
    B --> E["التكلفة c(x,y) هي c(y,x)"];
    C --> F["الحافة (x,y) ليست بالضرورة (y,x)"];
    C --> G["التكلفة c(x,y) قد تختلف عن c(y,x)"];

In the context of شبكات تينن, particularly as noted in your source, we will be focusing on and using undirected graphs in upcoming examples. This simplifies many calculations and analyses because you don't need to consider two separate directions for each connection.

3. Worked Example

Let's say we have three locations in a network: المدينة أ (City A), المدينة ب (City B), and المدينة ج (City C).

If this is an undirected graph:

• Connecting المدينة أ to المدينة ب has a cost c(أ,ب) = 5 units (e.g., 5 dinars or 5 milliseconds).
• Because it's undirected, the connection from المدينة ب to المدينة أ automatically has the same cost: c(ب,أ) = 5 units.
• Similarly, if the connection from المدينة ب to المدينة ج costs c(ب,ج) = 12 units, then c(ج,ب) also equals 12 units.

There's no extra information needed for the reverse direction; it's inherently the same.

4. Key Takeaways

• Undirected graphs treat connections ((x,y)) as interchangeable with their reverse ((y,x)).
• The cost of an edge is the same regardless of which direction you traverse it in an undirected graph.
• This characteristic simplifies network analysis as you only need to define each connection once.
• Directed graphs allow for distinct connections and costs in each direction.
• Your upcoming network examples will primarily use undirected graphs.

Common Mistakes to Avoid:

• Assuming c(x,y) is always different from c(y,x) in all graphs; this is only true for directed graphs.
• Trying to assign separate costs to (x,y) and (y,x) in an undirected graph – it's redundant.
• Forgetting that the undirected nature means the "path" is symmetrical in terms of cost and existence.
• Confusing the terminology: knowing "undirected" means no directionality in edges or costs.

5. Now Try It

Think of a small network of 4 computers (Computer 1, Computer 2, Computer 3, Computer 4). Assume this is an undirected graph. You are given the following connection costs:
* Computer 1 to Computer 2: 10
* Computer 1 to Computer 3: 7
* Computer 2 to Computer 4: 15
* Computer 3 to Computer 4: 8

Your task:
1. List all the unique connections you can make between any two computers based on this information, explicitly stating both directions where applicable.
2. State the cost for each direction.

What success looks like: You should have a clear list demonstrating that for each given connection, the reverse connection exists and has an identical cost, without needing new information.