Imagine an organization that wants to set up teams of three to work on some projects.
In order to maximize the number of people on each team who had previous experience working
together successfully, the director asked the members to provide names of their previous partners.
This information is displayed below both in a table and in a diagram.
From the diagram, it is easy to see that Bev, Cai, and Flo are a group of three previous partners,
and so it would be reasonable for them to form one of these teams.
• This drawing shows that placing Hal on the same team as Ed would leave Gia and Ira on a
team where they would not have a previous partner.
Graphs
Drawings such as these are known as a graph.
•
The dots are called vertices (plural of vertex)(정점)
•
The line segments joining vertices are called edges (변)
– The edges may be straight or curved and should either connect one vertex to another or a vertex to itself
In general, a graph consists of a set of vertices and a set of edges connecting various pairs of vertices.
The vertices are usually labeled with v’s and the edges with e’s.
•
When an edge connects a vertex to itself (e5), it is called a loop.
•
When two edges connect the same pair of vertices (e2 and e3), they are said to be parallel.
•
It is quite possible for a vertex to be unconnected by an edge to any other vertex in the graph (v5), and in that case the vertex is said to be isolated.
Directed Graphs
We have discussed the directed graph of a binary relation on a set.
A directed graph is like an (undirected) graph except that each edge is associated with an
ordered pair of vertices rather than a set of vertices.
Thus each edge of a directed graph can be drawn as an arrow going from the first vertex to the
second vertex of the ordered pair.
Degree of vertex
The degree of a vertex can be obtained from the drawing of a graph by counting
how many end segments of edges are incident on the vertex
SubGraph
A graph H is said to be a subgraph of a graph G if, and only if, every vertex in His also a vertex in G, every edge in H is also an edge in G, and every edge in H has the same endpoints as it has in G.
Complete Graph
Complete graph: all pairs of vertices are connected by edges.
Definition of walk, trail, path, and circuit
Trees
A tree is a connected graph that does not contain any circuits.
Rooted Trees
A rooted tree is a tree in which there is one vertex that is distinguished from the others and is called the root. The level of a vertex is the number of edges along the unique path between it and the root. The height of a rooted tree is the maximum level of any vertex of the tree. Given the root or any internal vertex v of a rooted tree, the children of v are all those vertices that are adjacent to v and are one level farther away from the root than v. If w is a child of v, then v is called the parent of w, and two distinct vertices that are both children of the same parent are called siblings.
Given two distinct vertices v and w, if v lies on the unique path between w and the root, then v is an ancestor of w and w is a descendant of v.
Binary Trees
When every vertex in a rooted tree has at most two children and each child is designated either
the (unique) left child or the (unique) right child, the result is a binary tree.
Spanning Tree
Minimum spanning tree
More generally, a graph whose edges are labeled with numbers (known as weights) is called a weighed graph.
A minimum-weight spanning tree, or simply a minimum spanning tree, is a spanning tree for which the sum of the weights of all the edges is as small as possible.
