4.1 Graphs and Terminology

 .remove_background_ad { border: 1px solid #555555; padding: .75em; margin: .75em; background-color: #e7e7e7; } .rmbg_image { max-height: 80px; } What are the two foundations of a graph? They consist of vertices and edges. What does the notation G=(V,E) mean? G = the graphV = the set of vertices(nodes)E = the set of edges. How many endpoints can a single edge have? An edge can be connected to either one or two vertices(nodes) What is a simple graph? 3 things. A graph where1. Each edge connects to two different nodes2. Two nodes only has one direct way to connect with each-other, not two or more. 3. What is a multi-graph? What is the multiplicity of a pair of nodes? If is equal to how many edges that connects the two nodes in the pair. What is a directed graph? explain each part of the notiation G=(V,E) G= the graphV= the set vertecies/nodesE= is the ordered set, collection, of edges between the nodes. When are two vertices adjacent? Two nodes are adjecent when they are connected by and edge,called incident. (just normal edge) What is the set called neighborhood of a node? N(v) is = the set of all nodes that are adjacent to the node v What is the degree of vertex? node In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. What is an isolated vertex? How many degrees does it have? It has no connections, no adjacent nodes and therefor degree 0 When is a vertex pendant? A vertex is pendant if and only if it hasdegree one. Consequently, a pendant vertex is adjacent to exactly one other vertex. What is the handshaking theorem? Use on G=(V,E) and let G be an un-directed graph with m edges Finnish the sentance " an un-directed graph has an X number of vertices of y degree" " an undirected graph has an even number of vertecies of odd degree" What is meant by terminal vertex? The vertex a is the initial vertex of the edge and b the terminal vertex.so terminal vertex just means the end point(node) of an edge What is in-degree of a vertex? it means how many edges has this node as its endpoint?