Help: Graph Theory Formula for Gzn Edges w/z & n

In summary, Gzn can be defined as a graph with n vertices where each vertex is a subset of Y containing z elements. The number of edges in this graph can be calculated using the formula n!/[z!(n-z)!]*(z*(z-1))/2.
  • #1
TinyTex
7
0
z = positive int, Y = {1 2 3 ... n} where Y = n greater or equal to z
defines Gzn

1)work out a formula in n and z for the edges in G zn, the vertex set to include all possible z elements subsets of Y

help please what's the formula?
i know how to work out the number of vertices in a formula
which is n!/z!(n-z)!
been stuck on the formula for the edges for ages... i also know how to calculate the edges if its a complete graph e.g. G1n is n(n-1)/2 since degree (v)= doubles the edges

e.g. G23 has 3 vertexs of {12}{13}{23} no edges
 
Last edited:
Physics news on Phys.org
  • #2
The formula for the number of edges in Gzn is n!/[z!(n-z)!]*(z*(z-1))/2. This formula is derived from the number of combinations of z elements subsets of Y and the fact that each of these combinations has z(z-1)/2 edges between them.
 

FAQ: Help: Graph Theory Formula for Gzn Edges w/z & n

What is the purpose of graph theory?

Graph theory is a branch of mathematics that studies the properties and relationships of graphs, which are mathematical structures used to model pairwise relations between objects.

What is the formula for calculating the number of edges in a graph with z nodes and n edges?

The formula for calculating the number of edges in a graph with z nodes and n edges is E = n(z-1)/2. This formula is known as the handshaking lemma and is based on the fact that each edge is connected to two nodes, so the total number of edges is half of the sum of the degrees of all the nodes.

How is graph theory used in real-life applications?

Graph theory has a wide range of applications in various fields such as computer science, biology, social sciences, and transportation networks. It is used to model and analyze complex systems, find the shortest path between two points, and optimize networks.

What is the difference between a directed and an undirected graph?

In a directed graph, the edges have a specific direction, indicating a one-way relationship between the nodes. In an undirected graph, the edges do not have a direction, and the relationship between the nodes is bidirectional.

What is the importance of understanding graph theory?

Understanding graph theory is important because it provides a powerful tool for modeling and solving real-world problems. It also helps in understanding complex networks and their properties, which can lead to more efficient and optimized systems.

Back
Top