Chap 2

• Graph theory traces its origin to the Königsberg Bridge Problem solved by Leonhard Euler in 1736
• Graph theory has applications in printed circuit and microchip design
• A graph consists of a set of objects where some pairs are connected by links, with interconnected objects represented by points termed as vertices and the links that connects the vertices are called as edges
• A graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges connecting the pairs of vertices
• A path in a graph is a sequence of vertices and edges from one vertex to another
• A graph is connected if there is a path between every pair of distinct vertices
• There are two types of graphs: directed and undirected
• In a directed graph, each vertex has an indegree and an outdegree
• Indegree of a vertex is the number of edges coming into the vertex, denoted as deg−(V)
• Outdegree of a vertex is the number of edges going out from the vertex, denoted as deg+(V)
• A point is a particular position in a one-dimensional, two-dimensional, or three-dimensional space
• V={a,b,c,d} and E=∅.

  
• V={a,b,c,d} and E={{a,b},{a,c},{b,c},{c,d}}

  
• Line is a connection between two points. It can be represented with a solid line
• Vertex is a point where multiple lines meet. It is also called a node
• Pendent Vertex is a vertex with degree one

  
• Is a vertex with degree zero is called an isolated vertex

  
• Edge is the mathematical term for a line that connects two vertices
• If an edge is drawn from vertex to itself, it is called a loop

  
• A graph G′(V′,E′) is a subgraph of the graph G(V,E) if V′⊆V and E′⊆E. Note that this does require G′(V′,E′) to be a graph, so one cannot form a subgraph of arbitrary subsets of V and E. (The second graph below is a subset of the first)

  
• Graph Connectedness is connected if it has no parts that are isolated from each other, if you can get from each part to every other part

  
• Directed Graph each vertex has an indegree and an outdegree

  
• Undirected graph has no directed edges

  
• Graphs can be classified as weighted (with values in edges) or unweighted (without values in edges)