### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Graph Theory WApplics MATH 4315

UH

GPA 3.69

### View Full Document

## 56

## 0

## Popular in Course

## Popular in Mathmatics

This 3 page Class Notes was uploaded by Alvena McDermott on Saturday September 19, 2015. The Class Notes belongs to MATH 4315 at University of Houston taught by Staff in Fall. Since its upload, it has received 56 views. For similar materials see /class/208434/math-4315-university-of-houston in Mathmatics at University of Houston.

## Popular in Mathmatics

## Reviews for Graph Theory WApplics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15

INFORMAL OUTLINE OF COMPLEXITY GRAPH THEORY MATH 4315 A decision problem is a question stated in a form in which it has a yes 7 or no 7 answer Here are a few typical examples Colorabz39lz39ty Instance G a graph k an integer Question Is chromatic number of G g k ie is it possible to color vertices of a graph with at most k colors so that adjacent vertices have different colors 73rz39mality Instance n an integer Question Is n prime Independence Instance G a graph k an integer Question Is the independence number of G 2 k Eulerz39an Tour Instance G a graph Question Is it possible to list edges of G so that each edge appears on the list exactly once and each of them apart from the rst one is incident with the previus edge on the list Hamiltonian Path Instance G a graph Question Is it possible to list vertices of G so that each appears on the list once and every vertex is adjacent to the previus one on the list E1 Is there a polynomial time algorithm to decide if a nite graph is connected E2 Is there a polynomial time algorithm to decide if a nite graph is Eulerian Ten Instance D a Diophantine equation ie7 a multi variable polynomial equation with integer coef cients Question ls D solvable in integers NP is the class of decision problems for which the answer is 77yes77 and for which there is an answer whose correctness can be veri ed in a polynomial time The latter means that there is an algorithm ie7 a program P which on input consisting of an evidence of correctness will con rm that the answer to the question is 77yes77 after running time t5 0sk for some integer k In this de nition 5 is the size of the input problem7 ie7 a measure of its complexity Size can be de ned in many ways7 and the only essential factor is not to 77in ate77 its de nition too much Size of the problem can be thought of as the minimum amount of information needed to describe this problem A right size for most of decision problems involving graphs is either the number of its vertices or its edges Note7 that as far as the existence of polynomial time algorithms is concerned7 it does not matter which one of the two is selected7 as long as the graph is connected However7 it may not be obvious at rst that for Primalz ty the right size is not 717 but logn lndeed7 an integer n can be de ned basically by logn units of information7 namely the digits of n tn Of means that there is a constant C such that for all suf ciently large 717 l tn l S Cfn Thus tn 0nk for an integer k means that It grows slower than some polynomial Note that the number of digits representing n with respect to any base is Ologn NP stands for the class of nondeterministic polynomial decision problems The class 73 is the class of decision problems which can be solved in a polynomial time From a highly theoretical point of view polynomial time algorithms are considered quick or ef cient Certainly can not be solved in polynomial time computationally intractable Such problems are called exponential It is not known whether classes 73 and N73 are equal7 but it is thought that they are not To prove this would be enough to show that for example Colorabz39lz39ty does not belong to 73 and in particular that there is no polynomial time algorithm for nding the chromatic number of a graph To show that Colorabz39lz39ty belongs to N73 it is enough to observe that if one can guess a right coloration of a graph then the correctness of the coloration can be indeed quickly veri ed In other words a right coloration can be presented as an evidence of correctness of the 77yes77 answer 3 More interestingly if there is a polynomial time algorithm for nding chromatic number of a graph then this would imply that every problem in N73 can be solved in a polynomial time and in particular that 73 N73 Decision problems which have this property an which are in N73 are called NP complete Many problems studied in graph theory including all three examples listed above are NP complete An example of a problem which belongs to 73 and thus certainly is not NP complete is the question whether a graph is Eulerian Pratt proved in 775 that Primalz ty belongs to N73 but it is not know whether there is a polynomial time algorithm for testing whether integer is a prime Pratt7s Theorem answered one of the very few non trivial open problems concerning membership in N73 As far as the tests and the material from this section are concerned you may expect only questions concerning decision problems for which there are polynomial time algorithms as for example E1 and E2

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.