Hire Experts For Answers

Order Now#### Related Study Services

- Homework Answers
- Coursework writing help
- Term paper writing help
- Writing Help
- Paper Writing Help
- Research paper help
- Thesis Help
- Dissertation Help
- Case study writing service
- Capstone Project Writing Help
- Lab report Writing
- Take my online class
- Take my online exam
- Do my test for me
- Do my homework
- Do my math homework
- Online Assignment Help
- Do my assignment
- Essay Writing Help
- Write my college essay
- Write my essay for me

DESCRIPTION

Posted

Modified

Viewed
15

Hello, I need help with a homework for Graph Algorithm please. I want it to be bigger than 14 points and it needs to be done in latex. I offer money for it.

This order does not have tags, yet.

Attachments

Homework 2 - november 12, 2021
Deadline: 07:00 am, november 19, 2021, by e-mail delivery
- The homework can be solved by teams of at most two students.
- LaTeX (correctly) written solutions will receive a bonus of 2 points.
- Don’t write again the texts of the problems! Each problem needs at most 1 or 1
and a half pages.
- ANY COPIED SOLUTION FOR A PROBLEM FROM BELOW WILL RECEIVE
−2 POINTS.
- The solutions will be delivered by e-mail until 07:00 am, november 19, 2021, at one
of the following addresses: olariu@info.uaic.ro, fe.olariu@gmail.com
- The e-mail must contain the source (a .doc, .odt or .tex file) and the .pdf file, both
with the following name format:
Name1 group Name2 group Homework1.tex (or .doc, .odt)
Name1 group Name2 group Homework1.pdf
- Examples:
IonescuPVasile A8 VasilescuTIon X1 Homework1.tex (or .doc, .odt, .pdf)
IonescuPVasile B6 VasilescuTIon E5 Homework1.tex (or .doc, .odt, .pdf)
1. You are given a set of cities, along with the pattern of highways between them, in the form of
an undirected graph G = (V,E). Each stretch of highway e ∈ E connects two of the cities, and you
know its length, ce. You want to get from city s to city t (s, t ∈ V , s 6= t). There’s one problem: your
car can only hold enough gas to cover L km. There are gas stations in each city, but not between
cities.
a) Show how to determine in O(|V |+ |E|) time complexity whether there is a feasible route from
s to t (a route you can ride using your car).
b) You are now planning to buy a new car, and you want to know the optimum (hence minimum)
distance you can ride with a full fuel tank in order to travel from s to t given the circumstances.
Give an efficient algorithm to determine this.
(2 + 2 = 4 points)
2. Let G = (V,E) be a connected graph and c : E → R an injective cost function defined on its
edges. For a spanning tree T of G and u, v ∈ V we denote by ET (u, v) the set of edges of the unique
path from u to v in T ; an edge uv ∈ E is called T -red if there exists an edge xy ∈ ET (u, v) such that
c(uv) < c(xy).
(a) Let T be a spanning tree of G such that there exists a T -red edge in G. Prove that T is not of
minimum cost.
(b) Let T be a spanning tree of G such that there is no T -red edge in G. Let T ′ be another spanning
tree of G (T 6= T ′). Then there exists a sequence of spanning trees T = T1, T2, . . . , Tk = T ′ such
that Ti+1 = Ti− ei + e′i, where ei ∈ E(Ti) and e′i ∈ E(T ′), and c(Ti+1) > c(Ti), for all 1 6 i < k.
(c) Let T be a spanning tree of G. Prove that T is a minimum cost spanning tree of G if and only
if there is no T -red edge in G.
(d) Using the above results prove that G contains only one minimum cost spanning tree.
(1 + 3 + 1 + 1 = 6 points)
3. Let G = (V,E) be a graph and H a subgraph of G. A H-chain in G is a cycle or a path of non-
zero length of G, P , which intersects H only in its endpoints (if P is a cycle, then |V (P )∩V (H)| = 1,
otherwise |V (P ) ∩ V (H)| = 2). A c-decomposition of G is a sequence of graphs, G1, G2, . . . , Gp
(p > 1) such that
(i) G1 is a cycle and Gp = G;
(ii) for each 1 6 i < p, there exists a Gi-chain in Gi+1, Pi, such that V (Gi+1) = V (Gi) ∪ V (Pi) and
E(Gi+1) = E(Gi) ∪ E(Pi).
(a) Prove that G (|G| > 3) is 2-edge-connected if and only if there exists a c-decomposition of G.
*
Consider now the following algorithm:
for (v ∈ V )
label[v]← −1; parent[v]← 0; E [v]← ∅;
// E[v] (a queue) will contain backward edges starting in v.
k ← 0; S.push(s); label[s]← 0;
// S is a stack containing s.
for(i = 1, n)
vertex[i]← 0;
vertex[1]← s;
while(S 6= ∅){
u← S.top();
if(v ← A[u].next 6= null)
if(label[v] < 0)
k + +; S.push(v); parent[v]← u;
label[v]← k; vertex[k]← v;
else
E [v].push(vu);
else
S.delete(u);
}
for(v ∈ V )
visited[v]← 0;
i← 0;
for(k = 1, n) {
x← vertex[k];
if(visited[x] = 0) {
visited[x]← 1;
while(E [x] 6= ∅) {
xy ← E [x].pop(); i + +; Pi ← {xy};
while(visited[y] = 0)
Pi ← Pi ∪ {parent[y]y};
y ← parent[y];
visited[y]← 1;
}
}
}
(b) For a 2-edge-connected graph G = (V,E) prove that the algorithm builds a c-decomposition of
G. What is its time complexity?
(c) Show how to modify this algorithm in order to decide if its input, the graph G = (V,E), is
2-edge-connected.
(3 + 2 + 1 = 6 points)

Explanations and Answers
0

No answers posted

### Post your Answer - free or at a fee

**NB: **Post a homework question for free and get answers - free or paid homework help.

Get answers to: Homework For Graph Algorithms or similar questions only at Tutlance.

Related Questions

- Reverse Engineering Assembly Code Bomb Lab
- Operating Systems - File System
- Need Help With Java Program Hangman
- Write A Program That Implements The Davis-Putnam Algorithm.
- Linux Driver - Kernel C Programming
- Intro To Compsci, Python Assignment, Nothing Beyond Introductory Python Stuff.
- Public Key Encryption And Aes Encryption
- Create A Computer Program Using C++ Basic Language To Check The Strength Of A Password
- Assembly Language Programming Help
- 3 Java Arraylist Problems And Dataset
- Implement The Given C File In Mips Assembly. Using Mars 4.5
- Neural Net Back Propagation Error Calculations
- Python Socket Programming Dictionary Attack
- Macro Assignment In Two Ways For The Following
- Data And Database Management With Sql
- Udp Client Socket Programming In Python
- Linux Command Line Using Vim And Bash
- The Questions Are All About Parallel Processing
- Reading Accelerometer Data Using Stm32F411
- Computer Systems Architecture.
- Msc Projuct: An Investigation Into The Cyber Security Risks Of Home\Small Business Setups
- Create A Class Called 'Indexedlist' Which Encapsulates A [Simplified] Index-Based List Collection.
- One Python Programming Question. Robot Olympics Club
- Python Programming Assignment Questions
- Need Help With A Simple C++ Assignment
- Math Foundations For Computer Science
- The Project Is Almost Complete!
- Algorithm Question/ Pseudocode
- Computer Security Principle And Practice By William Stallings 4Th Edition
- Data Structure / Java Project / Computer Science
- Your Job In This Lab Is To Write Mymalloc.c, Which Implements The Procedures Defined In Mymalloc.h:
- Someone Can Help Me On It ? ????????????????????
- Subnet Taple And Cisco Command
- Computer Maths In Jupyter Notebook
- Computer Architecture Assembly
- Create Time Class That Supports Custom Operations
- Worked Examples To Formal Logic Questions
- Write A Program Using Pep9 Using Assembly Language
- Creating A Java Program That Includes Methods In Sorting Algorithms.
- Please I Need Help Cooding In Python
- Computability And Complexity Assignment
- Assignment/Report On An Organisation
- Java Programming Assignment. Knowledge Of Sorting Algorithms.
- Comp Sci Assignment Due At 12 Today
- Data Flow Analysis Need To Be Submitted Tomorrow Oct 24 ( From Programming Language Analysis)
- C++, Java Or Python The Modification Should Be Significant, Requiring A Change In Both Syntax And Semantics
- Converting A C Program Into Mips Assembly Program Using Mars4.5
- I Need Help With Fundamentals Of Computer Systems Homework
- Finishing A Pascal Program That Is A Translation Of A C Program
- C++ College Homework: Implement The Rsa Encryption/Decryption Algorithm