krit.club logo

Algebra - Networks: edges, arcs, nodes, and paths-extended

Grade 9IB

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

A Network (or Graph) consists of a set of points called Nodes (or Vertices) and connections called Edges (undirected) or Arcs (directed).

•

The Degree (or Valency) of a node, denoted by d(v)d(v), is the number of edges connected to it. For directed arcs, we distinguish between 'in-degree' and 'out-degree'.

•

A Walk is a sequence of edges where the end of one edge is the start of the next. A Path is a walk where no node is visited more than once.

•

A Cycle is a closed path where the start and end nodes are the same, and no other nodes are repeated.

•

A Tree is a connected network with no cycles. A Spanning Tree is a subgraph that includes all nodes of the original network and is a tree.

•

A network is Planar if it can be drawn in a plane without any edges crossing each other.

•

The Handshaking Lemma states that the sum of the degrees of all nodes is exactly twice the number of edges: ∑d(v)=2E\sum d(v) = 2E.

📐Formulae

∑i=1ndeg(vi)=2E\sum_{i=1}^{n} \text{deg}(v_i) = 2E

V−E+F=2(Euler’s Formula for planar networks)V - E + F = 2 \quad \text{(Euler's Formula for planar networks)}

Max Edges (Simple Graph)=n(n−1)2\text{Max Edges (Simple Graph)} = \frac{n(n-1)}{2}

Edges in a Tree=V−1\text{Edges in a Tree} = V - 1

💡Examples

Problem 1:

A network has 55 nodes with degrees 2,3,3,4,2, 3, 3, 4, and 22. Calculate the number of edges in this network.

Solution:

Using the Handshaking Lemma: Sum of degrees=2+3+3+4+2=14\text{Sum of degrees} = 2 + 3 + 3 + 4 + 2 = 14 Since ∑d(v)=2E\sum d(v) = 2E: 14=2E14 = 2E E=142=7E = \frac{14}{2} = 7

Explanation:

The sum of all node degrees is always twice the number of edges because every edge contributes one degree to each of the two nodes it connects.

Problem 2:

Determine if a simple graph can exist with 44 nodes where the degrees are 1,2,3,1, 2, 3, and 33.

Solution:

Sum of degrees: 1+2+3+3=91 + 2 + 3 + 3 = 9 According to the Handshaking Lemma, the sum of degrees must be an even number because ∑d(v)=2E\sum d(v) = 2E.

Explanation:

Since 99 is an odd number, it is impossible to have a graph with these specific degrees. The number of nodes with odd degrees must always be even.

Problem 3:

In a connected planar network, there are 66 nodes and 1010 edges. How many faces (FF) does the network have?

Solution:

Using Euler's Formula: V−E+F=2V - E + F = 2 Substitute the given values: 6−10+F=26 - 10 + F = 2 −4+F=2-4 + F = 2 F=2+4=6F = 2 + 4 = 6

Explanation:

Substitute the number of nodes (V=6V=6) and edges (E=10E=10) into the formula V−E+F=2V - E + F = 2 and solve for FF.