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
multi-graph.

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.

Annonser

Om mattelararen

Licentiate of Philosophy in atomic Physics Master of Science in Physics
Det här inlägget postades i Algebra, Gymnasiematematik(high school math), Uncategorized. Bokmärk permalänken.

Kommentera

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

WordPress.com Logo

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

Twitter-bild

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

Facebook-foto

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

Google+ photo

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

Ansluter till %s