More Graphtheory

More graph-terminology:
The distance between two nodes is the shortest distance between the two nodes.
A graph that starts and ends in the same node is called a cycle or a closed circuit.
A simple path trespasses every node only once.

Let n be a node in a graph or multigraph G. The degree or valence of v is the number of arcs having an endpoint in v.
This number can be written as deg(v).
The handshaking lemma: At a large party where everybody shakes hand but not with everybody the number of persons having shaken hand an odd number of times is even.

a graph where it is allowed to pass a node several times is called a

a complete graph is a graph without loops and where every pair of nodes are connected with an arc.

Ex. Let G be a loop-free graph with n nodes, such that G has 175 arcs and its complement has 56 arcs. Determine n.
Solution: The totla number of arcs in G and its complement equals the number of arcs in the complete graph Kn.
Therefore 175 + 56 = n(n-2)/2 or ”n over 2” &imp; 231 = n(n-1)/2 &imp; n=22 ∧ n=-21.

Om mattelararen

Licentiate of Philosophy in atomic Physics Master of Science in Physics
Detta inlägg publicerades i Algebra, Gymnasiematematik(high school math), Uncategorized. Bokmärk permalänken.


Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

Du kommenterar med ditt Logga ut /  Ändra )


Du kommenterar med ditt Twitter-konto. Logga ut /  Ändra )


Du kommenterar med ditt Facebook-konto. Logga ut /  Ändra )

Ansluter till %s