(а)/bd\cdad(b)сесеaeafac(2)de(3)(4)(5)df(6)PP/(1)Figure 1: (a) A map where the cost of every edge is 1. Initially the pursuer P is at node band the evader E is at node d. (b) A partial game tree for this map. Each node is labeledwith the P, E positions. P moves first.2. True or False?(a)(A ^ B) = (A + B)(C V (¬A^ ¬B)) = ((A→C) ^ (B → C))(A V B) ^ (¬C V ¬D V E) = (A V B)(A V B) ^ ¬(A =→ B) is satisfiable.(b)(c)3.Prove using Venn diagram, or find a counterexample to the following as-sertion:a F (B^^) then a = ß and a =

Answered: Image /qna-images/answer/ffdfb334-15aa-4185-8916-f658777ee98e.jpg

Engineering

Computer Science

b

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

(c) A graph is represented as an adjacency matrix A, where A[i, j] = 1 denotes that there is an undirected edge between vertexes i and j; and A[i, j] = 0 otherwise, i,j = 1,2, ..., N. Write an algorithm to read the adjacency matrix and output the corresponding adjacency lists to represent the graph.
[0, 0, 2, 11, 9, 1, 3, 2) 1, 10, 0o, 0o, 0, 3, 0, 3, 0, 0o, 0, 0o, 0o, 3, 7, 0] a) Draw the above directed graph in the space besides the matrix b) For the graph above, determine the all-pair shortest path distance for all vertices (from all vertices). c) Determine the shortest path between vertices 1 to 3.
2. [20 points][MID] The graph k-coloring problem is stated as follows: Given an undirected graph G = (V, E) with N vertices and M edges and an integer k. Assign to each vertex v in V a color e(r) such that 1 < e{u) < k and c(u) # c(v) for every edge (u, v) in E. In other words you want to color each vertex with one of the k colors you have and no two adjacent vertices can have the same color. For example, the following graph can be 3-colored using the following color assignments: a=1,b=2,c=1,d%32,e=3,f=2.g33 a---b---c---g d Formulate the graph k-coloring problem as an evolutionary optimization. You may use a vector of integer representation, OR any representation that you think is more appropriate. you should specify: • A representation. • itness function. Give 3 examples of individuals and their fitness values if you are solving the above example. A set of mutation and/or crossover and/or repair operators. Intelligent operators that are suitable for this particular domain will earn…
(V, E) be a connected, undirected graph. Let A = V, B = V, and f(u) = neighbours of u. Select all that are true. Let G = a) f: AB is not a function Ob) f: A B is a function but we cannot always apply the Pigeonhole Principle with this A, B Odf: A B is a function but we cannot always apply the extended Pigeonhole Principle with this A, B d) none of the above
2. (Error-correcting codes x planarity.) Let n be a positive integer. Define the graph H, as follows: • Vertices: the set of all length-n strings over the alphabet {0, 1, 2}. • Edges: draw an edge from string s to string t if the Hamming distance dy(s, t) is 1. (a) Draw H2 (no justification needed.) (b) Prove that for every n 2 3, H, is nonplanar.
[Problem 6] Consider an undirected graph G = (V, E), in which each edge has the identical weight. Consider a minimum spanning tree of the graph G, called T = (V, E'). For each question below, draw a picture and then formally show that a) there is a unique path between u and u in T for all u, v € V. b) tree T is not unique. You must provide a formal proof AND an illustrative picture
discrete structure
None
also find its average path length
(V, E) be an undirected graph. Assume that the vertices 2. Let G represent documents. The edges are weighted so that w(i, j) is the dissimilarity between documents i and j. It is desired to partition the vertices into k > 3 disjoint clusters such that k ΣΣ υ(u, υ). i=1 (u,v)EE u,vEC; is minimized. The set C; is the set of documents in cluster i. Show that the e-approximate version of this problem is P-hard for all e, e > 0. Note that k is a fixed integer provided with each problem instance and may be different for different instances.
(9) An undirected weighted graph G is given below: a d 5 2 3 6 لها b 8 5 7 e 1 4 3 с 6 3 4 f 4 4 h 2 8 Use Prim's algorithm to compute the minimum spanning tree for the weighted graph. Start the algorithm at vertex a.
ExpressF(A,B,C,D) = Σm(1,3,4,6,9,11,12,14) + Σd(2,8,10,15) inPOS using K-MAP