Graphs And Trees

Edges, vertices, trees. As per Discrete Mathematics With Applications, Susanna S. Epp.

58 flashcards · Mathematics · by lakesare

1. What 2 sets and function define a graph?

   V(G) - { vertices of a graph } E(G) - { edges of a graph } edge-endpoint function: associates each edge to { 1 or 2 vertices }

2. What's a loop?

   Edge that's only associated with { 1 vertex }.

3. What edges are considered parallel?

   Distinct edges that are associated with { same set of vertices }

4. What vertices are considered adjacent? What edges are considered adjacent?

   Vertices are adjacent: if they are connected by edge. Edges are adjacent: if they connect to the same vertex.

5. What's a directed graph (digraph)?

   Directed graph is just like a usual graph, but each edge is associated with a 1/2-tuple of vertices instead of a set. 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.

6. What's a simple graph?

   Graph what doesn't have any loops or parallel edges. That is, every edge is associated with unique { 2 vertices }. Isolated vertices are allowed! In a simple graph, an edge with endpoints v and w is denoted {v, w}. A simple graph, also called a strict graph is an undirected graph containing no graph loops or multiple edges. A simple graph may be either connected or disconnected.

7. What's a complete graph?

   Simple graph, where exactly one edge connects each distinct { 2 vertices }.

8. Draw a complete graph with 4 vertices.

9. What's a degree of a vertex deg(v)?

   Amount of edges incident on this vertex (with an edge that's a loop counting twice). (Basically amount of lines sticking out of the vertex)

10. What's deg(v3)? What's deg(G)?

    deg(v3) = 3 deg(G) = 4

11. State handshake theorem.

    deg(G) = deg(v1) + deg(v2) + ··· + deg(vn) = 2 · (amount of edges of G) Sum of the degrees of all the vertices of any graph G equals twice the number of edges of G. Corollary is that a total degree of a graph is always even.

12. Prove that there exists no simple graph with four vertices of degrees 1, 1, 3, 3

13. Is it possible in a group of 9 people for each to be friends with 5 others?

    deg(G) = 5 lines out of 9 people = 45. Handshake theorem states that deg(G) = 2 · amount_of_edges. Since 45 is not even, it's not possible.

14. Prove a handshake theorem: deg(G) = 2 · (amount of edges of G)

    Let's prove that each edge contributes exactly 2 degrees to the deg(G). Edge can be connected either to { 2 vertices }, or { 1 vertex }. In each case it will contribute 2 degrees to deg(G) by definition.

15. In any graph G. There is an EVEN amount of vertices of ODD degree. Prove!

    deg(G) = deg(even-degree vertices) + deg(odd-degree vertices) deg(G) is even (by handshake theorem). deg(even-degree vertices) is even (even-degree * some number of vertices) => even = even + deg(odd-degree vertices) => deg(odd-degree vertices) is even. QED.

16. Is there a graph with ten vertices of degrees 1, 1, 2, 2, 2, 3, 4, 4, 4, and 6?

    Nope! Amount of odd-number-degree vertices must be even. But it's 3 here.

17. Draw it:

18. Find all edges that are incident on v1. Find all vertices that are adjacent to v3. Find all edges that are adjacent to e1. Find all loops. Find all parallel edges. Find all isolated vertices. Find the degree of v3. Find the total degree of the graph.

    e1, e2, and e3 are incident on v1. v1, v2, and v3 are adjacent to v3. e2, e8, e9, and e3 are adjacent to e1. Loops are e6 and e7. e8 and e9 are parallel; e4 and e5 are parallel. v6 is an isolated vertex. degree of v3 = 5 total degree = 20

19. What are: strict graph undirected graph multiple edges connected/disconnected graph

    strict graph - same as simple graph undirected graph - when edges are associated with a set (rather than a tuple) of edges { v1, v2 } multiple edges - parallel edges (two or more edges that are incident to the same two vertices) connected/disconnected graph - if there exist two nodes such that no path in G has those nodes as endpoints A simple graph, also called a strict graph is an unweighted, undirected graph containing no graph loops or multiple edges. A simple graph may be either connected…

20. Strict vs simple vs complete vs connected graphs?

    strict, simple - graph with no loops/parallel edges, but can be both connected and disconnected complete - each vertex is connected to every other vertex connected - every subgraph is connected by some path

21. What is a trail from vertice v to w?

    A trail from v to w is a walk from v to w that does not contain a repeated edge.

22. What is a path from vertice v to w?

    A path from v to w is a trail that does not contain a repeated vertex.

23. Closed walk VS Circuit?

    A closed walk is a walk that starts and ends at the same vertex. A circuit is a closed walk that contains at least one edge and does not contain a repeated edge. A simple circuit is a circuit that does not have any other repeated vertex except the first and last. Because most of the major developmentsin graph theory have happened relatively recently and in a variety of different contexts, the terms used in the subject have not been standardized. For example, what this book calls a graph is some…

25. What's connected component?

    A connected component of a graph is a connected subgraph of largest possible size. This graph has 3 connected components: A graph that is itself connected has exactly one connected component, consisting of the whole graph.

26. What's an Euler circuit of a graph?

    Euler circuit is circuit that contains every vertex and every edge of G, each edge only once.

27. What's meant by a digraph?

    Directed graph.

28. What's meant by a length of a walk in a graph?

    Number of edges in it. The length of a walk in a graph is the number of edges in it. The length of a directed walk in a digraph is the number of arcs in it.

29. Explain what is what on this adjacency matrix

    Row and column labels represent vertices. Matrix entry represents whether some vertex is adjacent (1) or not (0) to another vertex.

30. How to calculate the number of walks of length 2 from vertice 2, to vertice 6?

    Construct the adjacency matrix of this graph A, and then calculate A2. Number of walks will be in the entry A2,6 (or A6,2). In this case, number of walks is 3.

31. Represent with the adjacency list.

    For each vertex i, store an array of the vertices adjacent to it. Or, in javascript: [ [1, 6, 8], [0, 4, 6, 9], [4, 6], [4, 5, 8], [1, 2, 3, 5, 9], [3, 4], [0, 1, 2], [8, 9], [0, 3, 7], [1, 4, 7] ]

32. What is a path graph?

    The path graph is a tree with two nodes of vertex degree 1, and the other nodes of vertex degree 2. A path graph is therefore a graph that can be drawn so that all of its vertices and edges lie on a single straight line.

33. What is a cycle graph?

    A cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3) connected in a closed chain. Cycle graph has to have at least 3 edges.

34. How to read this?

    Graph G is defined by a set of vertices V, and set of edges E. Order of V is n, meaning number of vertices in G is N.

35. Explain sentence All cycle graphs are 2-regular

    Every vertex in a cycle graph has a degree of 2 (which's true!).

36. When do we call a graph cyclic?

    When graph has at least one cycle subgraph!

37. State 2 properties a graph must have in order to be a tree.

    It must be connected (it's called a forest otherwise) It must have no circuits

38. Find all terminal vertices and all internal vertices in the following tree:

    The terminal vertices are v0, v2, v4, v5, v7, and v8. The internal vertices are v6, v1, and v3.

39. State 2 main theorems about trees (how many edges does a tree with n vertices have?).

    1. For any positive integer n, any tree with n vertices has n − 1 edges. 2. For any positive integer n, if G is a connected graph with n vertices and n − 1 edges, then G is a tree.

40. A graph G has ten vertices and twelve edges. Is it a tree?

    No. By Theorem 10.5.2, any tree with ten vertices has nine edges, not twelve. ■

41. What's a rooted tree?

    A rooted tree is a tree in which there is one vertex that is distinguished from the others and is called the root.

42. What's meant by level VS height in a rooted tree?

    The level of a vertex - is the number of edges along the unique path to the root. The height of a rooted tree - is the maximum level of any vertex of the tree.

43. What is the level of v5? What is the level of v0? What is the height of this rooted tree?

    What is the level of v5? - 2 What is the level of v0? - 0 What is the height of this rooted tree? - 3

44. What are the children of v3? What are the descendants of v3?

    Children of v3 are: v5 and v6 Descendants of v3 are: v5, v6, v10 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. 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.

45. When is tree a binary tree? (2 qualities)

    it's rooted each node has at most 2 children, and they are directed (left and right) In mathematics, what is termed binary tree can vary significantly from author to author. Some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and don't necessarily order (as left/right) the children either.

46. What's meant by a full binary tree?

    A full binary tree is a binary tree in which each parent has exactly 2 children.

47. If T is a full binary tree with k internal vertices, how many terminal vertices does T have?

    T has k + 1 terminal vertices.

48. Is there a full binary tree that has: 10 internal vertices and 13 terminal vertices?

    No. By Theorem 10.6.1, a full binary tree with 10 internal vertices has 10 + 1 = 11 terminal vertices, not 13.

49. Any tree with n vertices has n − 1 edges. Full binary tree with k internal vertices, has k+1 terminal vertices.

50. Let G be the following graph and let v be the vertex indicated Draw G - v.

    Let G be a graph and v be a vertex of G. Then G − v is the graph we obtain by deleting v and all edges incident to v from G.

51. Place these numbers in a binary search tree:

    We go one by one, inserting smaller nodes to the left, and bigger nodes to the right.

52. What's the algorithm for storing data in a balanced binary search tree?

53. What's the difference between cycle graph and a cyclic graph?

    Cycle graph (or circular graph) - consists of a single cycle, or in other words, some number of vertices (at least 3) connected in a closed chain. Cyclic graph - cyclic graph may mean a graph that contains a cycle, or a graph that is a cycle, with varying definitions of cycles.

54. Name 3 ways to represent a graph.

    adjacency matrices incidence matrices adjacency lists

55. Build incidence matrix for a graph.

    Note Incidence matrices are not suitable for any digraph with a self-loop (‘loop’ for short).

56. Build adjacency list for a digraph.

    In an adjacency list representation, a graph G = (V, E) is represented by an array of lists, one for each vertex in V . For each vertex u in V , the list contains all the vertices adjacent to u in an arbitrary order, usually in increasing or decreasing order for convenience. Why an adjacency list?It is space efficient for sparse graphs where the number of edges is much less than the squared power of the number of vertices.

57. Build adjacency matrix for a graph.

58. What's weighted graph?

    A weighted graph is a graph in which every edge is associated with a real value as its weight (or cost). A weighted graph is a graph in which each branch is given a numerical weight. A weighted graph is therefore a special type of labeled graph in which the labels are numbers (which are usually taken to be positive).