All Matches

Solution Library

Expert Answer

Textbooks

Search Textbook questions, tutors and Books

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Tutors
Study Help
Hire a Tutor
AI Study Help New

Search
Sign In
Register

study help
mathematics
introduction to the mathematics

Questions and Answers of Introduction To The Mathematics

Find the optimal vehicular flow for the traffic network with capacities below. Do this problem by hand, rather than in Mathematica. m Exercise 8
Let the intermediate nodes on the graph of Exercise 1 represent switching locations at a busy train station located at node 5 , to which trains are arriving from node 1.The edge capacities represent
The graph of Exercise 15 of Section 1.2 modeling a forced-air heat distribution system is displayed again below, with one additional edge. This time we suppose the fully connected system exists and
The diagram below represents the lubrication system of a machine; the lubricant flows from a source area at node 1 , through components \(2-6\), which require lubrication, and collects at node 7 .
Devise a graph in which at some step the maximal flow algorithm will reduce the flow along a reverse edge.
Implement your own version of the AddFlow command described in this section.
In the problem of Example 3, suppose that in breadth-first search, vertex 4 is labeled first, before vertex 2 , so that vertex 3 will be labeled by vertex 4 rather than vertex 2 . Carry out the
Call a directed graph double quasi-connected if each pair of vertices has not only a common ancestor, but also a common descendant. Show that a double quasi-connected graph has both a root and a
Find all maximal trees and maximal paths for the graph of Figure 1.2.
Find all critical paths for the graph of Exercise 12 of Section 1.3 whose adjacency matrix is as below. Do this by hand, rather than with Mathematica. 4 3 4 2 936 5 2 215 622 4234 -
A job requires ten stages of work. The completion times for each are in the table below. Also listed in the table is the information of which stages cannot begin until other stages are complete,
Finish the proof of Theorem 2 by showing assertion 2: If \((u, v)\) is an omitted edge and \(S(u, v)=0\), then the spanning tree created by substituting \((u, v)\) for the edge \(\left(u_{0},
A large computer program is to be tested and debugged in modules, some of which require other modules to be completely tested before testing on them can proceed. The table below shows the
Intuitively, it is clear what we mean when we say that a graph is a "line of vertices" (see below). Give a set-theoretic definition of a line of vertices, and show that if a directed network is not a
An office wants to install an information system. The main tasks are below, with time estimates in days and task dependencies indicated. Find the amount of time required to get the system up and
An advertising agency has contracted to prepare a commercial. The main tasks, time estimates, and task dependencies are shown in the table below. How many days will it take to produce this
For the project in Exercise 4, form a project graph with tasks on vertices.
A variation on the critical path problem is the task scheduling problem. In this problem, unlike the critical path problem, explicit attention is paid to how many workers are available to do tasks,
Use Kruskal's algorithm to find a minimal cost spanning tree for a graph whose vertices are labeled \(\{1,2, \ldots, 8\}\) and whose edges have the costs below: 146 51 25 321 1321 - - - - 2 - 21 -
Cables are to connect several components of a sound system. The vertices in the graph below represent the components, and the edges are possible connections. The matrix above gives the lengths of
In Example 2 compute the cost of the spanning trees formed by (a) breadth-first search; (b) ordering edges lexicographically. By how much do these costs differ from the total cost of the minimal
Suppose that the distances between fifteen cities are as in the table below, An airline wishes to institute service among these cities. Assuming that flight cost is directly proportional to distance,
Show that if a weighted, undirected graph \(G\) is connected and no two of its edges have the same cost, then there is a unique minimal spanning tree.
Explain why every vertex has component number 1 at the end of execution of Kruskal's algorithm.
Prove or disprove. Let \(T\) be a minimal spanning tree of an undirected graph \(G\) and fix a vertex \(v_{0}\). Then for each vertex \(u eq v_{0}\), the cost of the path in \(T\) from \(v_{0}\) to
An amusement park wishes to run a tram line among several of its rides. The rides are nodes in the graph below, and the weights of the edges are distances between the nodes. Design a connecting
An alternative algorithm for finding a minimal undirected spanning tree of a graph of \(n\) vertices is called Prim's algorithm. Begin with a single vertex. At any stage, check edges not in the
Prove that Prim's algorithm of Exercise 9 yields a minimal spanning tree if the graph is connected. (Hint: Prove by induction that at each step the subgraph created by Prim's algorithm is connected
Information is to flow from a source \(v_{0}\) to each of seven other locations labeled \(v_{1}, \ldots, v_{7}\) in the diagram below. Find a least costly way of doing this if the edge weights
The matrix below gives the weights of directed edges connecting certain pairs of vertices in a directed graph. List shortest possible paths from vertex 1 to each other vertex in the network. 1215 121
The vertices in the graph below are grain elevators, some of which can be connected by chutes to neighboring elevators, for the purpose of shifting grain from one location to another. The edges are
An alternative algorithm for finding the shortest path from the root \(v_{0}\) to each vertex \(v\) in a directed graph, called Dijkstra's algorithm, is as follows. Initialize the cost \(C(v)\) of a
Prove that if a quasi-connected, directed graph with root \(v_{0}\) and positive costs is input to Dijkstra's algorithm (see Exercise 14), then for each \(v eq v_{0}\), a shortest path from \(v_{0}\)
Use Dijkstra's algorithm (see Exercise 14) to list shortest paths to all vertices \(v_{1}, \ldots, v_{7}\) in the graph of Exercise 11 Do this by hand, rather than with Mathematica.
A reservoir at vertex 1 in the diagram below is to supply water to several pumping stations. The edge weights are costs of laying pipe from one station to another. How should the pipe be laid so that
Find a spanning tree of the graph below using the undirected spanning tree algorithm. Work by hand on this problem rather than using Mathematica. Assume that the order of the edges
what spanning tree does the Spanning Tree One Step function find when the order of edges is:(a)
Suppose that \(G=(V, E)\) is a connected graph and \(\{u, v\} \in E\) is an edge in some cycle. Show that the graph \(G^{\prime}=(V, E)-\{u, v\}\) is connected. (This fact was used in the proof of
Prove that a connected, undirected graph \(G\) is a tree if and only if for each edge \(\{u, v\} \in G, G-\{u, v\}\) is not connected.
The graph below shows computer links between an official vote-tallying center at vertex 1 and several precincts. For the sake of secrecy, links can be made secure, but since this is an expensive
Prove that if \(G\) is an undirected tree with more than one vertex, then \(G\) contains at least two vertices of degree 1 .
Finish the proof of Theorem 1, that is, if \(G\) is a connected graph with \(n\) vertices and \(n-1\) edges, then \(G\) is a tree.
Consider two connected components of an undirected graph \(G\), and suppose each has no cycles. Let \(G^{\prime}\) be a new graph whose vertex set is the union of the vertex sets of the two
Is it possible to construct an undirected tree whose eight vertices have degrees \(1,2,3,3,1,1,3\), and 2 , respectively? Why, or why not?
Write your own version of the Convert To Adj Matrix [edgelist, n] command without options, which takes a list of edges of an undirected graph and the number of vertices in the graph, and returns the
Using the work already done in creating the Spanning Tree One Step function, write a full, simplified version of the complete undirected spanning tree algorithm, without the options, which takes the
A complete undirected graph is a graph such that edges exist between every pair of vertices. Find an upper bound for the number of spanning trees a complete graph can have.
Find a directed spanning tree of the following graph if one exists. Is the tree unique? Do this by hand and not in Mathematica.
Vertices 8 and 18 are also roots in the graph of Figure 1.20. Check this using the Descendants function, and find directed spanning trees using each of these roots.
A forced-air heat distribution system in a building must get heat from the central furnace at vertex 1 in the figure to each of the rooms located at the other vertices. It is possible to mount
A directed graph has the adjacency matrix below. Use the Breadth First Tree function to find a directed spanning tree. Determine the root using the Descendants
Repeat Exercise 16 for the graph whose adjacency matrix is above. The root vertex is 7 .
Prove or disprove. A directed graph is a tree if and only if it is connected and has no directed cycles.
Prove or disprove. A directed graph is a tree if and only if it is quasi-connected and has no directed cycles.
Would the directed spanning tree algorithm also find an undirected spanning tree if the given graph was connected and undirected? Explain.
For the graph below, write the adjacency matrix \(A\), compute \(A^{3}\), and verify that for each \(i\) and \(j, A^{3}(i, j)\) is the number of paths from \(i\) to \(j\) of length 3 by listing those
Prove Theorem 1.
Show that the graph whose adjacency matrix is below has no cycles.\[ \left(\begin{array}{lllllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0
Show that there is no four-vertex undirected graph with degrees \(d\left(v_{1}\right)=3, d\left(v_{2}\right)=2, d\left(v_{3}\right)=2\), and \(d\left(v_{4}\right)=2\).
Write a Mathematica command that takes the adjacency matrix of a graph and a vertex, and returns the degree of that vertex. Test it on all the vertices of the graph of Figure 1.4.
Let \(A\) be the adjacency matrix of an undirected graph \(G\). Show that \(A^{2}(i, i)=d(i)\).
Two graphs \(G_{1}=\left(V_{1}, E_{1}\right)\) and \(G_{2}=\left(V_{2}, E_{2}\right)\) are called isomorphic if there is a one-to-one onto function \(f: V_{1} \rightarrow V_{2}\) such that for all
Argue, using the adjacency matrix only, that the graph in Figure 1.6 (a) is not connected.
There is a function in the KnoxOR`Graphs` package calledThis command returns a list of all children of vertices in the given list of parents, where adjmatrix is the adjacency matrix of a directed
Prove that if the vertex set of a directed graph can be partitioned into three subsets \(V_{1}, V_{2}\), and \(V_{3}\) such that edges only exist from \(V_{1}\) into \(V_{2}\), or from \(V_{2}\) into
Decide whether the following graph is (a) connected or (b) quasi-connected. ex12 = {{0, 1, 1, 0, 0}, {0, 0, 1, 1, 0}, {1, 0, 0, 0, 0}, (0, 0, 0, 0, 1}, {0, 1, 1, 1, 0}}; DisplayGraph[ex12, GraphType
Show that a connected directed graph is quasi-connected. Show that an undirected graph is quasi-connected if and only if it is connected.
For the graph of Figure 1.9, verify that \(A^{m}\) is not entirely non-zero for any \(m 3 2 Figure 1.9 - Paths of length 4 exist between each pair of vertices
Find all connected components of the graph below. 11 12 16
Argue that for undirected graphs, the connected components algorithm does find the connected component of the given initial vertex.
Prove that for directed graphs, the connected components algorithm finds the set of vertices that can be reached from a given initial vertex \(v\). Prove that this set is a closed set (see Example
For an undirected graph with the adjacency matrix below, find the connected components.\[ \left(\begin{array}{llllllllll} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
Write a Mathematica command that takes a weight matrix of a graph, and a list of vertices forming a path in the graph, and returns the weight of the path.
Adjacency matrices are not the only way of representing graphs. An adjacency list representation of a graph is a list, vertex-by-vertex, of the vertices that are adjacent to that vertex. For example,
Devise a way of implementing in Mathematica an adjacency list representation of a graph. (See Exercise 19.) Write a function that converts an adjacency list to an adjacency matrix.Data from in

Showing 500 - 600 of 575

1
2
3
4
5
6

Services

Sitemap
Fun
Definitions
Become Tutor
Study Help Categories
Recent Questions
Expert Questions

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Campus Ambassador

Secure Payment

Download Our App

© 2024 SolutionInn. All Rights Reserved