What is Vertex: Definition and 136 Discussions

In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory.
The minimum vertex cover problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem.
Vertex cover problems have been generalized to hypergraphs, see Vertex cover in hypergraphs.

View More On Wikipedia.org
Recent contents Top users
  1. T

    Calculating flux when charge on vertex of cube

    Homework Statement A point charge q = 112 x 10^-9 C is placed at the centre of a cube of side l = 0.2 m. If the charge is moved all the way to one vertex of the cube, determine the flux through each of the faces. Homework Equations None. The Attempt at a Solution I looked at...
  2. Telemachus

    Getting a rhombus vertex from one vertex and its area

    Hi there. I am tryin to solve this one, I know that if I find the way to get one more vertex i'd have it solved. Homework Statement The point A(-1,8) is the vertex of a rhombus which minor diagonal is situated on the line L: L=\begin{Bmatrix} x=3\mu & \mbox{ }& \\y=1+4\mu &...
  3. C

    How Do You Find the Y-Coordinate of a Parabola's Vertex?

    Homework Statement Sorry for such an elementary question, but I'm struggling thru Int Alg. Today's nightmare involves a downward parabola. An arch supporting a bridge has the equation y=-0.0022x^2 + 1.578x + 0. Position of left side parabolic arch is (0,0). Using x = -b/2a, I calculated the...
  4. B

    What is the correct charge conservation at a vertex in a decay process?

    Is my understanding correct: Charge is conserved at a vertex. So the charges of particles pointing in towards a vertex and the charges of particles pointing out must be equal. Alternatively: The sum of the charges at a vertex must be zero. So if this is correct, can someone explain the...
  5. A

    Help Needed: Graph Theory Assignment on Vertex Colouring

    I am working on graph theory assignment. I need help because I am not seeing where I am going with this question. Here's the question: G is a simple graph with n vertices. -> show that vertex colouring of G [ X(G) ]* vertex colouring of G complement >= n -> show that the vertex...
  6. S

    How is 0-cell is a vertex

    Definition: (open cell). Let X be a Hausdorff space. A set c ⊂ X is an open k − cell if it is homeomorphic to the interior of the open k-dimensional ball Dk = {x ∈ Rk | x < 1}. The number k is unique by the invariance of domain theorem, and is called dimension of c. A 0-cell, 1-cell...
  7. S

    Welcome Questions about MC Vertex

    Hi all Can someone tell me what is meant by an "MC Vertex"? I'm coming across it in some analysis code. Thanks.
  8. A

    Showing the Kneser graph is vertex transitive

    Homework Statement the kneser graph KG(n:k) is the graph whose vertices are all of the k-subsets of {1,2,...,n} with 2 vertices beign adjacent if they are disjoint. show KG(n:k) is vertex transitive Homework Equations a graph G is vertex transitive if for any 2 vertices x,y in G...
  9. T

    Can Anyone Explain How to Solve Vertex Correction for a W Boson?

    do anyone can help to solve this vertex correction for W boson? \frac{-ieg^{2}}{8(2\pi)^{4}}\int...
  10. Z

    Parabola (Horizontal) - finding vertex, focus and equation of line

    Homework Statement Use completing the square method to rewrite the equation of the parabola y^2 – 4y – 44 = 16x in the form (y-y0)^2 = 4A(x-x0) Hence find: a) the coordinates of the vertex b) the coordinates of the focus c) the equation of the line that passes through the focus...
  11. Saladsamurai

    Finding the Vertex Coordinates of a Rectangle In Cartesian Space

    I am hoping to find the coordiantes of all 4 vertices when the rectangle is in any orientaion knowing the length l, the width b, the coordinate of its center mark (xcen,ycen), and the coordinate of vertex A as shown below: This is NOT HOMEWORK so although I think it is possible to do, I am...
  12. J

    Distance from vertex to focus in a parabola

    Homework Statement I am a bit rusty on parabolae. I am doing a question on projectiles and have found the coordinates of the vertex of a parabola as: (\frac{(v_0)^2\sin\alpha\cos\alpha}{g},\frac{(v_0)^2(\sin^2\alpha)}{2g}) The question now requires you to show that the distance...
  13. A

    Quadratic Equations in Vertex Form

    Homework Statement Find the roots and the vertex for 3x^2 + 5x - 2 Homework Equations ax^2 + bx + c a(x - h) + k The Attempt at a Solution OK, this is what I attempted. 3x^2 + 5x - 2 = 0 3x^2 + 6x - x - 2 = 0 3x(x+2) - 1(x+2) = 0 x = 1/3 and x = -2 OK, so I found the roots...
  14. N

    Amplitude of Vertex Diagram: Unchanged?

    If the momenta on the three external legs p(incoming fermion), p'(outgoing fermion) and p-p' (photon) of a vertex diagram are replaced by -p, -p' and p'-p respectively (i.e., all the external momenta are multiplied by -1) does the amplitude remain unchanged?
  15. E

    Solve Lagrangian Deduc Vertex Problem Easily

    I want deduc vertex of the lagrangian, but I not know how?
  16. T

    Parabolic Equations Using Vertex & Focus

    Homework Statement Write the equation of the parabola described. Vertex: (2, 4) Focus: (2,6) Homework Equations (x-h)^2 = 4p(y-k) The Attempt at a Solution (x-2)^2 = 4(2)(y-4) x^2-4x+4 = 8y -32 Do I need to isolate one of the variables, or can I leave the equation like this?
  17. S

    Is there a network with 50 arcs annnd one vertex?

    Homework Statement Is there a network with 50 arcs and one vertex?
  18. C

    How to find the equation of a parabola with the following vertex.

    1. I need to find the equation of a parabola with a vertex of (-3,-2). It has to open down. 2. I understand of hopefully will understand it. 3. My answer was y=-3x Squared -3x-2 Which I found to be wrong.
  19. K

    Finding the Vertex of a Parabola: y = (x + 2)^2 - 3

    Homework Statement Identify the vertex of the parabola y = (x + 2)2 – 3 Homework Equations The Attempt at a Solution I would love to have an attempt but I have gone through my book and notes and I'm still confused on how to do this. If i could see an example even so i can work...
  20. K

    Is the Correct Delta Function for a QED Vertex \(\delta(p+q-k)\)?

    say I have a QED vertex with an anti-fermion (p) going in and a fermion (q) and photon(k) coming out. Since the momentum flow is supposed to be along the direction of particle number flow, wouldn't this mean that the delta function at that vertex would be \delta(-p-q-k) ? that doesn't seem to...
  21. Y

    Finding Parabola Equation with Vertex and X-Intercept

    Homework Statement How do you figure out the equation of a parabola by only knowing the vertex and ONE of the x intercepts Vertex: (0, -1920) X intercept: (96,0) Help=)
  22. M

    Where can I find vertex corrections for leptons at different momenta?

    I am currently studying particle collisions. Before I begin I need latest mass values of the leptons, bosons and quarks. However I have been told that I will need to slightly modify these due to vertex corrections. (Due to the incoming particles interacting before colliding, see attachment for...
  23. marcus

    Three papers about the new LQG vertex (Marseille)

    A detailed introduction of the new LQG spinfoam model---flipped version of the Barrett-Crane vertex amplitude---appeared in August*. Quite a lot of follow-up work has been posted, including three papers that appeared yesterday. Recently posted extensions include numerical work by Rovelli et al...
  24. S

    Find equation of a parabola when neither of two points is the vertex

    Can we find the equation of a parabola when two points on it and the time of travel between the two points are given.It is also given that neither of the two given points is the vertex.
  25. S

    Find vertex by completing the square-NASTY

    Homework Statement find the vertex by completing the square: f(x)=2x^2-4x+7 Homework Equations The Attempt at a Solution numerous attempts yet not one looks right. one was as such: y-7=2x^2-4x; y-7+4=2x^2-4x+4; y-3=2x^2-4x+4; y=2(x-2)^2 +3... I could see this as...
  26. marcus

    The LQG vertex amplitude (Rovelli, Engle, Pereira)

    this just out http://arxiv.org/abs/0705.2388 The loop-quantum-gravity vertex-amplitude Jonathan Engle, Roberto Pereira, Carlo Rovelli 6 pages "Spinfoam theories are hoped to provide the dynamics of non-perturbative loop quantum gravity. But a number of their features remain elusive. The best...
  27. R

    Charges on the vertex of a triangle

    Positive point-charges of +16.0 mC are fixed at two of the vertices of an equilateral triangle with sides of 1.30 m, located in vacuum. Determine the magnitude of the E-field at the third vertex. so...all the particles are in equalibrum so that means F=ma=0 so if i call the third vertex...
  28. marcus

    A new spinfoam vertex probably MIP for second quarter

    "A new spinfoam vertex" probably MIP for second quarter The new paper of Livine and Speziale could very well turn out to be the most influential paper of second quarter 2007. http://arxiv.org/abs/0705.0674 A new spinfoam vertex for quantum gravity A large part (perhaps majority) of research...
  29. P

    Finding Distance Between Focus & Vertex of Parabola

    How do you find the value of the distance between the focus and vertix for the parabola given by the equation 6x^2 + 8 = 2y.
  30. H

    Show that in every simple graph there is a path from any vertex of odd degree to some other vertex of odd degree?

    please help me with this question Show that in every simple graph there is a path from any vertex of odd degree to some other vertex of odd degree? here is my answer please check and correct if its wrong thanx ANSWER: In a simple graph, the sum of the degrees of the vertices must...
  31. K

    Find the vertex, focus, and the directrix of the parabola

    Find the vertex, focus, and the directrix of the parabola. I get tripped up sometimes, but I know how to find all of the stuff with an equation like this : (x+1)^2 +8(y+3) = 0 But how do I find it with equations like this y^2=-6x or x+y^2=0 Can you complete the square with...
  32. N

    Draw graphs for self-energy and Vertex functions

    Could anyone help/advise me please how to draw graphs for self-energy and Vertex functions given in attachments one and two. In attachment one Sigma is self energy in coordinate space, S - fermion propagator, here I have one question: I was reading something where I found these exppresions, but...
  33. T

    Parabola with Focus (-5,0) & Vertex (-5,-4): Find Equation

    Fins an equation for the parabola with focus at (-5,0) and vertex at (-5,-4). I have come up with: x^2 + 10x + 16y + 89 = 0 How far off am I?
  34. D

    Finding the vertex of a parabola from an equation

    I need help with the following question. The parabola y^2 - x + 4y + k = 0 passes through the point (12,1). Find the vertex of the parabola.
  35. P

    What is the angle between the planes VBHD and ABDEFGH?

    1.In the figure, describe the motion of particles X and Y at the instant. What will be the shape of the string after 1/4 cycle? I don't know which direction that the crests are traveling as there are two sources. 2.The tetrahedron BCDH is cut off from the cube and is then placed on top of the...
  36. A

    Where Can I Find a Proof for the Four Vertex Theorem?

    Can somebody please give me an online reference for a good proof of 'The Four Vertex Theorem'? :confused:
Back
Top