| Degree (graph Theory) |
Article Index for Degree |
Website Links For Degree |
Information About ™Degree (graph Theory) |
|
In Graph Theory , the degree (or '''valency''') of a Vertex is the number of Edges Incident to the vertex. The degree of a vertex is denoted . UNDIRECTED GRAPHS For an Undirected Graph , the degree of a vertex is the number of edges incident to the vertex. This means that each Loop is counted twice. This is because each edge has two endpoints and each endpoint adds to the degree. The graph shown to the right has the following degrees: DIRECTED GRAPHS In a Directed Graph , an edge has two distinct ends: a head (the end with an arrow) and a tail. Each end is counted separately. The sum of head endpoints count toward the indegree and the sum of tail endpoints count toward the '''outdegree'''. The indegree is denoted and the outdegree as The image to the right has the following degrees: SPECIAL CASES OF DEGREE VALUE Isolated vertex If a vertex has a zero degree then it is called an Isolated Vertex . Leaf vertex If a vertex has a unity degree then it is a Leaf . This is fairly common in Trees in graph theory and Trees in Data Structure s. Regular graph If each vertex of the graph has the same degree the graph is called a ''k''-regular Graph and the graph itself is said to have degree . Source A vertex with is called a source. This name comes from the fact that the node is the origin/source of all of its incident edges. In the image under #Directed Graphs , vertex 1 is a source node. Sink A vertex with is called a sink. Similarly to source nodes, a sink gets its name from the fact that the node is the termination/destination/sink of all of its incident edges. In the image under #Directed Graphs , vertex 2 is a sink node. Euler tour A graph is Eulerian if and only if every vertex is of even degree. SOME THEOREMS The Degree Sum Formula states that, given a graph , |
|
|